Datenstrukturen und Algorithmen in JavaScript (4): String (BF)

Eine Zeichenfolge ist eine endliche Folge von null oder mehr Zeichen, auch Zeichenfolge genannt

Die logische Struktur einer Zeichenfolge ist der einer linearen Tabelle sehr ähnlich. Der Unterschied besteht darin, dass eine Zeichenfolge ein Zeichensatz ist und sich daher erheblich von der einer linearen Tabelle unterscheidet. Lineare Tabellen konzentrieren sich mehr auf die Operation CURD eines einzelnen Elements, während sich Strings auf Operationen wie das Finden der Position von Teilstrings und deren Ersetzen konzentrieren.

Natürlich haben verschiedene Hochsprachen unterschiedliche Definitionen grundlegender Zeichenfolgenoperationen, aber im Allgemeinen ist das Wesen der Operationen ähnlich. Beispielsweise ist die Javascript-Suche „indexOf“, das Entfernen von Leerzeichen ist „trimmen“, die Umwandlung von Groß- und Kleinschreibung in „LowerCase“/ „toUpperCase“ usw.

Hier besprechen wir hauptsächlich einige klassische Algorithmen für den String-Mustervergleich: BF, BM, KMP

BF (Brute Force)-Algorithmus

Grundidee des Brute-Force-Algorithmus:

Vergleichen Sie das erste Zeichen der Zielzeichenfolge s mit dem ersten Zeichen der Musterzeichenfolge t. Wenn sie gleich sind, fahren Sie mit dem Vergleich der nachfolgenden Zeichen nacheinander fort. Beginnen Sie andernfalls mit dem zweiten Zeichen der Zeichenfolge s und beginnen Sie erneut die Zeichenfolge t. Machen Sie einen Vergleich.

Und so weiter, bis jedes Zeichen in der Zeichenfolge t einer fortlaufenden Zeichenfolge in der Zeichenfolge s entspricht, gilt der Mustervergleich als erfolgreich. Zu diesem Zeitpunkt ist die Position des ersten Zeichens der Zeichenfolge t in der Zeichenfolge s t-Position in s, andernfalls schlägt der Mustervergleich fehl

Es ist ersichtlich, dass der BF-Algorithmus ein Brute-Force-Algorithmus ist, der auch als naiver Matching-Algorithmus oder Brute-Force-Algorithmus bezeichnet wird.

Hauptstrang BBC ABB ABCF

Teilzeichenfolge ABC

Das Finden der Position des Teilstrings im Hauptstring entspricht der Implementierung der indexOf-Suchmethode von Javascript

var sourceStr = "BBC ABB ABCF";
var searchStr = "ABC";

function BF_Ordinary(sourceStr, searchStr) {
 var sourceLength = sourceStr.length;
 var searchLength = searchStr.length;
 var padding   = sourceLength - searchLength; //循环的次数
 //BBC ABB ABCF =>ABC => 搜索9次
 for (var i = 0; i <= padding; i++) {
  //如果满足了第一个charAt是相等的
  //开始子循环检测
  //其中sourceStr的取值是需要叠加i的值
  if (sourceStr.charAt(i) == searchStr.charAt(0)) {
   //匹配成功的数据
   var complete = searchLength;
   for (var j = 0; j < searchLength; j++) {
    if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {
     --complete
     if (!complete) {
      return i;
     }
    }
   }
  }
 }
 return -1;
}

Nach dem Login kopieren

Der BF-Algorithmus ist einfach und grob. Er entnimmt direkt die Tabelle unten für jedes Zeichen der übergeordneten Zeichenfolge von BBC ABB ABCF und gleicht sie mit dem ersten Zeichen der Musterzeichenfolge ab

Hier ist es erwähnenswert:

1: Die Häufigkeit der äußersten Schleife sourceLength – searchLength, da die übergeordnete Zeichenfolge, die wir abgleichen, mindestens größer oder gleich der Teilzeichenfolge

sein muss

2: Beim fortgesetzten Abgleich von Teilzeichenfolgen muss der Startpunkt der übergeordneten Zeichenfolge überlagert werden (i j)

3: Bestimmen Sie anhand einer Bedingung, ob die Übereinstimmung vollständig ist. In BBC ABB ABCF müssen wir überspringen, wenn wir uns in ABB befinden

Der obige Algorithmus ist der einfachste und es gibt bessere Verarbeitungsmethoden im Code. Beispielsweise kann der Inversionsalgorithmus zum Abgleichen von Selbstzeichenfolgen verwendet werden

Optimierungsalgorithmus (1)

function BF_Optimize(sourceStr, searchStr) {
  var mainLength  = sourceStr.length;
  var searchLength = searchStr.length;
  var padding   = mainLength - searchLength;
  for (var offset = 0; offset <= padding; offset++) {
   var match = true;
   for (var i = 0; i < searchLength; i++) {
    //取反,如果只要不相等
    if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
     match = false;
     break;
    }
   }
   if (match) return offset;
  }
  return -1;
}

Nach dem Login kopieren

Wir müssen die Situation nicht als wahr beurteilen, wir müssen sie nur als falsch beurteilen. Wenn das Spiel nach Abschluss des Unterspiels nicht geändert wird, bedeutet dies, dass es sich um ein vollständiges Spiel handelt

Wir haben in den beiden oben genannten Methoden Unterschleifen verwendet. Können wir sie in einen Schleifenkörper umwandeln?

Tatsächlich können wir sehen, dass die Hauptzeichenfolge jedes Mal nur um 1 erhöht wird und die Unterzeichenfolge jedes Mal von Anfang an angepasst wird, sodass wir sie in eine Weile ändern und den Indexzeiger steuern können 🎜>

Optimierungsalgorithmus (2)

function BF_Optimize_2(sourceStr, searchStr) {
 var i = 0,
   j = 0;

  while (i < sourceStr.length) {
    // 两字母相等则继续 
    if (sourceStr.charAt(i) == searchStr.charAt(j)) {
     i++;
     j++;
    } else { // 两字母不等则角标后退重新开始匹配 
     i = i - j + 1; // i 回退到上次匹配首位的下一位 
     j = 0; // j 回退到子串的首位 
    }

    if (j == searchStr.length) {
     return i - j;
    }

  }
}

Nach dem Login kopieren

i ist die tiefgestellte Positionierung der Hauptzeichenfolge, j ist die tiefgestellte Positionierung der Teilzeichenfolge

Wenn die Hauptzeichenfolge und die Teilzeichenfolgen gleich sind, wird in den Schleifenmodus der Teilzeichenfolge gewechselt. Wenn die Anzahl der Unterschleifen j der Länge der Teilzeichenfolge entspricht, wird überprüft, ob es sich um eine vollständige Übereinstimmung handelt

Wenn die Hauptzeichenfolge und die Unterzeichenfolge nicht gleich sind, müssen Sie den Index der Hauptzeichenfolge um ein Bit nach hinten verschieben. Wenn i verwendet wird, kann es natürlich von der Unterzeichenfolge verarbeitet werden, sodass i-j 1 erforderlich ist. und dann wird der Teilstring zurückgesetzt

Für Details können wir uns den Codevergleich ansehen

Vier Strukturen basierend auf dem BF-Algorithmus, for/while/recursion

<!doctype html>由于电脑性能的不断提高，测试的数据量的大小，可能会导致得到的结果不太准确;<script type="text/javascript">

 /////////
 //暴力算法 //
 //普通版
 /////////
 function BF_Ordinary(sourceStr, searchStr) {
  var sourceLength = sourceStr.length;
  var searchLength = searchStr.length;
  var padding   = sourceLength - searchLength; //循环的次数

  //BBC ABB ABCF =>ABC => 搜索9次
  for (var i = 0; i <= padding; i++) {
   //如果满足了第一个charAt是相等的
   //开始子循环检测
   //其中sourceStr的取值是需要叠加i的值
   if (sourceStr.charAt(i) == searchStr.charAt(0)) {
    //匹配成功的数据
    var complete = searchLength;
    for (var j = 0; j < searchLength; j++) {
     if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {
      --complete
      if (!complete) {
       return i;
      }
     }
    }
   }
  }
  return -1;
 }


 /////////
 //暴力算法 //
 //优化版
 /////////
 function BF_Optimize_1(sourceStr, searchStr) {
   var mainLength  = sourceStr.length;
   var searchLength = searchStr.length;
   var padding   = mainLength - searchLength;
   for (var offset = 0; offset <= padding; offset++) {
    var match = true;
    for (var i = 0; i < searchLength; i++) {
     //取反,如果只要不相等
     if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
      match = false;
      break;
     }
    }
    if (match) return offset;
   }
   return -1;
 }


  ////////
  //优化版 //
  //while
  ////////
 function BF_Optimize_2(sourceStr, searchStr) {
  var i = 0,
    j = 0;

   while (i < sourceStr.length) {
     // 两字母相等则继续 
     if (sourceStr.charAt(i) == searchStr.charAt(j)) {
      i++;
      j++;
     } else { // 两字母不等则角标后退重新开始匹配 
      i = i - j + 1; // i 回退到上次匹配首位的下一位 
      j = 0; // j 回退到子串的首位 
     }

     if (j == searchStr.length) {
      return i - j;
     }

   }
 }


 /////////
 //暴力算法
 //递归版本
 /////////
 function BF_Recursive(sourceStr, searchStr, offset) {
   var mainLength = sourceStr.length;
   var searchLength = searchStr.length;
   if (searchLength > mainLength - offset) {
    return -1;
   }
   offset = offset || 0;
   for (var i = 0; searchLength > i; i++) {
    if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
     return BF_Recursive(sourceStr, searchStr, offset + 1)
    }
   }
   return offset;
 }


 
 var sourceStr = "There are some times wThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkhen clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer There are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely think that that Facebook would “definitely think about” adding a dislike button. “People definitely seem to want it,” Zuckerberg said. Four years later — Zuckerberg says Facebook is still “thinking about” adding the oft-requested sdfafd button, Zuckerberg says Facebook is still “thinking about” adding the oft-requested button. At a town hall meeting on Thursday, the CEO revealed he has some reservations about the feature. “There are two things that it can mean,” Zuckerberg said of the potential button, which could be used in a mean spirited way or to express empathy. Finding how to limit it to the latter is the challenge. Zuckerberg said he doesn't want the button to turn into a “voting mechanism” or something that isn't “socially valuable.” “Often people will tell us they don't feel comfortable pressing ‘like,'” Zuckerberg said. “What's the right way to make it so people can easier express a wide range of emotions&#63;” One suggestion percolating online: Aaron Roll out the feature under a different name. However, an “empathy button” just may not have the same ring to it as “dislike.”";
 var searchStr = "adding the oft-requested sdf";



 function show(bf_name,fn) {
  var myDate = +new Date()
  var r = fn();
  var div = document.createElement('div')
  div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms";
  document.body.appendChild(div);
 }

 show('BF_Ordinary',function() {
  return BF_Ordinary(sourceStr, searchStr)
 })

 show('BF_Optimize_1',function() {
  return BF_Optimize_1(sourceStr, searchStr)
 })

 show('BF_Optimize_2',function() {
  return BF_Optimize_2(sourceStr, searchStr)
 })

 show('BF_Recursive',function() {
  return BF_Recursive(sourceStr, searchStr)
 })

</script>

Nach dem Login kopieren

BF ist auch ein klassischer Präfix-Matching-Algorithmus. Der größte Nachteil dieses Algorithmus besteht darin, dass der Zeiger zurückverfolgt werden muss, sodass die Leistung sehr gering ist Schreiben Sie später über das Upgrade der KMP- und BM-Algorithmen für BF

Git-Code-Download:

https://github.com/JsAaron/data_structure

Datenstrukturen und Algorithmen in JavaScript (4): String (BF)_Javascript-Kenntnisse