Wie überprüfe ich, ob ein String vollständig aus demselben Teilstring besteht?

Ich muss eine Funktion erstellen, die eine Zeichenfolge akzeptiert, und sie sollte zurückgegeben werden trueoder darauf falsebasieren, ob die Eingabe aus einer wiederholten Zeichenfolge besteht. Die Länge der angegebenen Zeichenfolge ist immer größer als 1und die Zeichenfolge muss mindestens eine Wiederholung haben.

"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)

Ich habe die folgende Funktion erstellt:

function check(str){
  if(!(str.length && str.length - 1)) return false;
  let temp = '';
  for(let i = 0;i<=str.length/2;i++){
    temp += str[i]
    //console.log(str.replace(new RegExp(temp,"g"),''))
    if(!str.replace(new RegExp(temp,"g"),'')) return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

Dies zu überprüfen ist Teil des eigentlichen Problems. Ich kann mir eine solche nicht effiziente Lösung nicht leisten. Zuallererst durchläuft es die Hälfte der Saite.

Das zweite Problem ist, dass es replace()in jeder Schleife verwendet wird, was es langsam macht. Gibt es eine bessere Lösung für die Leistung?

Es gibt einen kleinen Satz über solche Saiten.

Eine Zeichenfolge besteht aus demselben Muster, das genau dann mehrmals wiederholt wird, wenn die Zeichenfolge eine nicht triviale Drehung von sich selbst ist.

Hier bedeutet eine Drehung, dass einige Zeichen von der Vorderseite der Zeichenfolge gelöscht und nach hinten verschoben werden. Zum Beispiel hellokönnte die Zeichenfolge gedreht werden, um eine dieser Zeichenfolgen zu bilden:

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

Um zu sehen, warum dies funktioniert, nehmen wir zunächst an, dass eine Zeichenfolge aus k wiederholten Kopien einer Zeichenfolge w besteht. Wenn Sie dann die erste Kopie des wiederholten Musters (w) von der Vorderseite der Zeichenfolge löschen und auf die Rückseite heften, erhalten Sie dieselbe Zeichenfolge zurück. Die umgekehrte Richtung ist etwas schwieriger zu beweisen, aber die Idee ist, dass Sie, wenn Sie eine Zeichenfolge drehen und das zurückbekommen, womit Sie begonnen haben, diese Drehung wiederholt anwenden können, um die Zeichenfolge mit mehreren Kopien desselben Musters zu kacheln (wobei dieses Muster das ist Zeichenfolge, die Sie zum Ende bewegen mussten, um die Drehung durchzuführen).

Nun stellt sich die Frage, wie überprüft werden kann, ob dies der Fall ist. Dafür gibt es einen anderen schönen Satz, den wir verwenden können:

Wenn x und y Zeichenfolgen gleicher Länge sind, ist x genau dann eine Drehung von y, wenn x eine Teilzeichenfolge von yy ist.

Als Beispiel können wir sehen, dass dies loheleine Rotation von hellowie folgt ist:

hellohello
   ^^^^^

In unserem Fall wissen wir, dass jeder String x immer ein Teilstring von xx ist (er erscheint zweimal, einmal bei jeder Kopie von x). Im Grunde müssen wir nur überprüfen, ob unsere Zeichenfolge x eine Teilzeichenfolge von xx ist, ohne dass sie beim ersten oder halben Zeichen übereinstimmt. Hier ist ein Einzeiler dafür:

function check(str) {
    return (str + str).indexOf(str, 1) !== str.length;
}

Angenommen, es indexOfwird ein schneller String-Matching-Algorithmus implementiert, der in der Zeit O (n) ausgeführt wird, wobei n die Länge des Eingabe-Strings ist.

Hoffe das hilft!

Sie können dies durch eine Erfassungsgruppe und eine Rückreferenz tun . Überprüfen Sie einfach, ob der erste erfasste Wert wiederholt wird.

function check(str) {
  return /^(.+)\1+$/.test(str)
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

In der obigen RegExp:

1. ^und $steht für Start- und Endanker , um die Position vorherzusagen.
2. (.+)Erfasst ein beliebiges Muster und erfasst den Wert (außer \n).
3. \1ist die Rückreferenz des ersten erfassten Werts und \1+würde auf Wiederholung des erfassten Werts prüfen.

Regex Erklärung hier

Für das RegExp-Debugging verwenden Sie: https://regex101.com/r/pqlAuP/1/debugger

Leistung: https://jsperf.com/reegx-and-loop/13

Der vielleicht schnellste algorithmische Ansatz besteht darin, eine Z-Funktion in linearer Zeit zu erstellen:

Die Z-Funktion für diese Zeichenfolge ist ein Array der Länge n, wobei das i-te Element gleich der größten Anzahl von Zeichen ist, beginnend mit der Position i, die mit den ersten Zeichen von s übereinstimmt.

Mit anderen Worten, z [i] ist die Länge des längsten gemeinsamen Präfixes zwischen s und dem Suffix von s, beginnend bei i.

C ++ - Implementierung als Referenz:

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

JavaScript-Implementierung
Optimierungen hinzugefügt - Erstellen einer Hälfte des Z-Arrays und vorzeitiges Beenden

function z_function(s) {
  var n = s.length;
  var z = Array(n).fill(0);
  var i, l, r;
  //for our task we need only a half of z-array
  for (i = 1, l = 0, r = 0; i <= n/2; ++i) {
    if (i <= r)
      z[i] = Math.min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
      ++z[i];

      //we can check condition and return here
     if (z[i] + i === n && n % i === 0) return true;
    
    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return false; 
  //return z.some((zi, i) => (i + zi) === n && n % i === 0);
}
console.log(z_function("abacabacabac"));
console.log(z_function("abcab"));

Dann müssen Sie Indizes überprüfen i, die n teilen. Wenn Sie dies finden i, kann i+z[i]=ndie Zeichenfolge sauf die Länge komprimiert werden iund Sie können zurückkehren true.

Zum Beispiel für

string s= 'abacabacabac'  with length n=12`

Z-Array ist

(0, 0, 1, 0, 8, 0, 1, 0, 4, 0, 1, 0)

und wir können das für finden

i=4
i+z[i] = 4 + 8 = 12 = n
and
n % i = 12 % 4 = 0`

Dies skönnte als Teilstring der Länge 4 dargestellt werden, der dreimal wiederholt wird.

Ich habe die Antwort von gnasher729 gelesen und implementiert. Die Idee ist, dass wenn es Wiederholungen gibt, es (auch) eine Primzahl von Wiederholungen geben muss.

function* primeFactors (n) {
    for (var k = 2; k*k <= n; k++) {
        if (n % k == 0) {
            yield k
            do {n /= k} while (n % k == 0)
        }
    }
    if (n > 1) yield n
}

function check (str) {
    var n = str.length
    primeloop:
    for (var p of primeFactors(n)) {
        var l = n/p
        var s = str.substring(0, l)
        for (var j=1; j<p; j++) {
            if (s != str.substring(l*j, l*(j+1))) continue primeloop
        }
        return true
    }
    return false
}

Ein etwas anderer Algorithmus ist folgender:

function check (str) {
    var n = str.length
    for (var p of primeFactors(n)) {
        var l = n/p
        if (str.substring(0, n-l) == str.substring(l)) return true
    }
    return false
}

Ich habe die jsPerf-Seite aktualisiert , die die auf dieser Seite verwendeten Algorithmen enthält.

Angenommen, die Zeichenfolge S hat die Länge N und besteht aus Duplikaten der Teilzeichenfolge s, dann teilt die Länge von s N. Wenn beispielsweise S die Länge 15 hat, hat die Teilzeichenfolge die Länge 1, 3 oder 5.

Sei S aus (p * q) Kopien von s. Dann besteht S auch aus p Kopien von (s, q-mal wiederholt). Wir haben daher zwei Fälle: Wenn N Primzahl oder 1 ist, kann S nur aus Kopien des Teilstrings der Länge 1 hergestellt werden. Wenn N zusammengesetzt ist, müssen wir nur Teilstrings s der Länge N / p auf Primzahlen p-Teilung prüfen die Länge von S.

Bestimmen Sie also N = die Länge von S und finden Sie dann alle seine Primfaktoren in der Zeit O (sqrt (N)). Wenn es nur einen Faktor N gibt, prüfen Sie, ob S dieselbe Zeichenfolge ist, die N-mal wiederholt wird. Andernfalls prüfen Sie für jeden Primfaktor p, ob S aus p Wiederholungen der ersten N / p-Zeichen besteht.

Ich denke, eine rekursive Funktion könnte auch sehr schnell sein. Die erste Beobachtung ist, dass die maximale Länge des wiederholten Musters halb so lang ist wie die gesamte Zeichenfolge. Und wir könnten einfach alle möglichen wiederholten Musterlängen testen: 1, 2, 3, ..., str.length / 2

Die rekursive Funktion isRepeating (p, str) testet, ob dieses Muster in str wiederholt wird.

Wenn str länger als das Muster ist, erfordert die Rekursion, dass der erste Teil (gleiche Länge wie p) eine Wiederholung ist, ebenso wie der Rest von str. So wird str effektiv in Stücke von Länge p.Länge zerlegt.

Wenn das getestete Muster und str gleich groß sind, endet die Rekursion hier erfolgreich.

Wenn die Länge unterschiedlich ist (passiert für "aba" und das Muster "ab") oder wenn die Teile unterschiedlich sind, wird false zurückgegeben, wodurch die Rekursion weitergegeben wird.

function check(str)
{
  if( str.length==1 ) return true; // trivial case
  for( var i=1;i<=str.length/2;i++ ) { // biggest possible repeated pattern has length/2 characters

    if( str.length%i!=0 ) continue; // pattern of size i doesn't fit
    
    var p = str.substring(0, i);
    if( isRepeating(p,str) ) return true;
  }
  return false;
}


function isRepeating(p, str)
{
  if( str.length>p.length ) { // maybe more than 2 occurences

    var left = str.substring(0,p.length);
    var right = str.substring(p.length, str.length);
    return left===p && isRepeating(p,right);
  }
  return str===p; 
}

console.log(check('aa')) //true
console.log(check('aaa')) //true 
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

Leistung: https://jsperf.com/reegx-and-loop/13

Schrieb dies in Python. Ich weiß, dass es nicht die Plattform ist, aber es hat 30 Minuten gedauert. PS => PYTHON

def checkString(string):
    gap = 1 
    index= 0
    while index < len(string)/2:
        value  = [string[i:i+gap] for i in range(0,len(string),gap) ]

        x = [string[:gap]==eachVal for eachVal in value]

        if all(x):
            print("THEY ARE  EQUAL")
            break 

        gap = gap+1
        index= index+1 

checkString("aaeaaeaaeaae")

Mein Ansatz ähnelt dem von gnasher729, da er die potenzielle Länge des Teilstrings als Hauptfokus verwendet, aber weniger mathematisch und prozessintensiv ist:

L: Länge der ursprünglichen Zeichenfolge

S: Mögliche Längen gültiger Teilzeichenfolgen

Schleife S von (ganzzahliger Teil von) L / 2 bis 1. Wenn L / S eine Ganzzahl ist, überprüfen Sie Ihre ursprüngliche Zeichenfolge anhand der ersten S-Zeichen der ursprünglichen Zeichenfolge, die L / S-mal wiederholt wurden.

Der Grund für das Schleifen von L / 2 rückwärts und nicht von 1 an besteht darin, den größtmöglichen Teilstring zu erhalten. Wenn Sie eine möglichst kleine Teilzeichenfolge von 1 bis L / 2 wünschen. Beispiel: "abababab" hat sowohl "ab" als auch "abab" als mögliche Teilzeichenfolgen. Welche der beiden Methoden schneller ist, wenn Sie sich nur um ein wahres / falsches Ergebnis kümmern, hängt von der Art der Zeichenfolgen / Teilzeichenfolgen ab, auf die dies angewendet wird.

Der folgende Mathematica-Code erkennt fast, ob die Liste mindestens einmal wiederholt wird. Wenn die Zeichenfolge mindestens einmal wiederholt wird, wird true zurückgegeben. Es kann jedoch auch true zurückgegeben werden, wenn die Zeichenfolge eine lineare Kombination wiederholter Zeichenfolgen ist.

IsRepeatedQ[list_] := Module[{n = Length@list},
   Round@N@Sum[list[[i]] Exp[2 Pi I i/n], {i, n}] == 0
];

Dieser Code sucht nach dem Beitrag "in voller Länge", der in einer sich wiederholenden Zeichenfolge Null sein muss. Die Zeichenfolge accbbdwird jedoch auch als wiederholt betrachtet, da es sich um eine Summe der beiden wiederholten Zeichenfolgen abababund handelt 012012.

Die Idee ist, die schnelle Fourier-Transformation zu verwenden und nach den Frequenzspektren zu suchen. Wenn man sich andere Frequenzen ansieht, sollte man auch dieses seltsame Szenario erkennen können.

Die Grundidee besteht darin, mögliche Teilzeichenfolgen zu untersuchen, beginnend bei Länge 1 und endend bei der Hälfte der Länge der ursprünglichen Zeichenfolge. Wir betrachten nur Teilzeichenfolgenlängen, die die ursprüngliche Zeichenfolgenlänge gleichmäßig teilen (dh str.length% substring.length == 0).

Diese Implementierung untersucht das erste Zeichen jeder möglichen Teilzeichenfolgeniteration, bevor zum zweiten Zeichen übergegangen wird. Dies kann Zeit sparen, wenn die Teilzeichenfolgen voraussichtlich lang sind. Wenn nach der Untersuchung des gesamten Teilstrings keine Nichtübereinstimmung festgestellt wird, geben wir true zurück.

Wir geben false zurück, wenn wir keine potenziellen Teilzeichenfolgen mehr zur Überprüfung haben.

function check(str) {
  const len = str.length;
  for (let subl = 1; subl <= len/2; ++subl) {
    if ((len % subl != 0) || str[0] != str[subl])
      continue;
    
    let i = 1;
    for (; i < subl; ++i)
    {
      let j = 0;
      for (; j < len; j += subl)
        if (str[i] != str[j + i])
          break;
      if (j != len)
        break;
    }
    
    if (i == subl)
      return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

Ich bin mit JavaScript nicht vertraut, daher weiß ich nicht, wie schnell dies sein wird, aber hier ist eine lineare Zeitlösung (unter der Annahme einer angemessenen integrierten Implementierung), die nur integrierte Funktionen verwendet. Ich werde den Algorithmus im Pseudocode beschreiben.

function check(str) {
    t = str + str;
    find all overlapping occurrences of str in t;
    for each occurrence at position i
        if (i > 0 && i < str.length && str.length % i == 0)
            return true;  // str is a repetition of its first i characters
    return false;
}

Die Idee ähnelt der Antwort von MBo. Für jedes i, das die Länge teilt, strist eine Wiederholung seiner ersten iZeichen genau dann, wenn es nach dem Verschieben für iZeichen gleich bleibt .

Ich denke, dass ein solches eingebautes System möglicherweise nicht verfügbar oder ineffizient ist. In diesem Fall ist es immer möglich, den KMP-Algorithmus manuell zu implementieren , der ungefähr dieselbe Codemenge benötigt wie der Algorithmus in MBos Antwort.

Eine der einfachen Ideen besteht darin, die Zeichenfolge durch die Teilzeichenfolge "" zu ersetzen. Wenn Text vorhanden ist, ist er falsch, andernfalls ist er wahr.

'ababababa'.replace(/ab/gi,'')
"a" // return false
'abababab'.replace(/ab/gi,'')
 ""// return true