Wie überprüfe ich, ob eine Zeichenfolge vollständig aus derselben Teilzeichenfolge besteht?

Ich muss eine Funktion erstellen, die eine Zeichenfolge übernimmt, und sie sollte zurückkehren true oder false basierend darauf, ob die Eingabe aus einer wiederholten Zeichenfolge besteht. Die Länge der angegebenen Zeichenfolge ist immer größer als 1 und 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 ineffiziente Lösung wie diese nicht leisten. Zunächst einmal wird es durch die Hälfte der Saite geloopt.

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

Es gibt ein nettes kleines Theorem über Strings wie diese.

Eine Zeichenfolge besteht aus demselben Muster, das mehrmals wiederholt wird, wenn und nur wenn die Zeichenfolge eine nicht triviale Drehung ihrer selbst ist.

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

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

Um zu sehen, warum dies funktioniert, nehmen Sie zunächst an, dass ein String aus k wiederholten Kopien eines Strings 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 zurückbekommen, was Sie begonnen haben, diese Drehung wiederholt anwenden können, um die Zeichenfolge mit mehreren Kopien desselben Musters zu kacheln (dieses Muster ist das Saite, die Sie zum Drehen ans Ende bewegen mussten).

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

Wenn x und y Strings gleicher Länge sind, dann ist x genau dann eine Rotation von y, wenn x ein Teilstring von yy ist.

Als Beispiel können wir das sehen lohel ist eine Rotation von hello folgendermaßen:

hellohello
   ^^^^^

In unserem Fall wissen wir, dass jeder String x immer ein Teilstring von xx sein wird (er erscheint zweimal, einmal bei jeder Kopie von x). Im Grunde müssen wir also nur prü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;
}

Vorausgesetzt indexOf mit einem schnellen String-Matching-Algorithmus implementiert wird, wird dieser in der Zeit O(n) ausgeführt, wobei n die Länge des Eingabe-Strings ist.

Hoffe das hilft!

Sie können es tun, indem Sie a Erfassungsgruppe und Rückverweis. Überprüfen Sie einfach, ob es sich um die Wiederholung des ersten erfassten Werts handelt.

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 jedes Muster und erfasst den Wert (außer \n).
3. \1 ist die Rückreferenz des ersten erfassten Werts und \1+ würde auf Wiederholung des erfassten Werts prüfen.

Regex-Erklärung hier

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

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

Der vielleicht schnellste algorithmische Ansatz ist das Erstellen von a Z-Funktion in linearer Zeit:

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

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 – Aufbau 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 die Indizes überprüfen i die n teilen. Wenn Sie solche finden i das i+z[i]=n dann die Saite s auf die Länge komprimierbar i und 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 finden für

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

Also s könnte als dreimal wiederholter Teilstring der Länge 4 dargestellt werden.

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

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 dieser:

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 aktualisiert jsPerf-Seite 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, dann hat die Teilzeichenfolge die Länge 1, 3 oder 5.

Sei S aus (p*q) Kopien von s aufgebaut. Dann besteht S auch aus p Kopien von (s, q mal wiederholt). Wir haben also zwei Fälle: Wenn N eine Primzahl oder 1 ist, dann kann S nur aus Kopien des Teilstrings der Länge 1 bestehen. Wenn N zusammengesetzt ist, müssen wir nur Teilstrings s der Länge N / p auf Primzahlen p teilend 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 Wiederholungsmusterlänge halb so lang ist wie die gesamte Saite. Und wir könnten einfach alle möglichen Wiederholungsmusterlä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, sowie der Rest von str. Also wird str effektiv in Stücke der Länge p.length 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 Muster „ab“) oder wenn die Teile unterschiedlich sind, wird „false“ zurückgegeben, wodurch die Rekursion nach oben propagiert 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

Habe das in Python geschrieben. Ich weiß, es ist nicht die Plattform, aber es hat 30 Minuten gedauert. PS => PYTHONE

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")