Jak sprawdzić, czy ciąg jest w całości wykonany z tego samego podciągu?

Muszę utworzyć funkcję, która przyjmuje ciąg znaków i powinna zwracać truelub w falseoparciu o to, czy dane wejściowe składają się z powtarzającej się sekwencji znaków. Długość podanego ciągu jest zawsze większa niż, 1a sekwencja znaków musi mieć co najmniej jedno powtórzenie.

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

Stworzyłem poniższą funkcję:

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

Sprawdzenie tego jest częścią prawdziwego problemu. Nie stać mnie na takie nieefektywne rozwiązanie. Po pierwsze, przechodzi przez połowę łańcucha.

Drugi problem polega na tym, że używa replace()w każdej pętli, co powoduje jej powolność. Czy istnieje lepsze rozwiązanie dotyczące wydajności?

Istnieje sprytne, małe twierdzenie na temat takich strun.

Łańcuch składa się z tego samego wzorca powtarzanego wielokrotnie wtedy i tylko wtedy, gdy struna jest nietrywialną rotacją samego siebie.

Tutaj obrót oznacza usunięcie pewnej liczby znaków z przodu ciągu i przeniesienie ich do tyłu. Na przykład ciąg hellomożna obrócić, aby utworzyć dowolny z następujących ciągów:

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

Aby zobaczyć, dlaczego to działa, załóżmy najpierw, że ciąg składa się z k powtórzonych kopii łańcucha w. Następnie usunięcie pierwszej kopii powtarzanego wzoru (w) z przodu sznurka i przyklejenie go do tyłu da z powrotem tę samą strunę. Odwrotny kierunek jest nieco trudniejszy do udowodnienia, ale chodzi o to, że jeśli obrócisz strunę i wrócisz do tego, od czego zacząłeś, możesz zastosować ten obrót wielokrotnie, aby podzielić ciąg z wieloma kopiami tego samego wzoru (ten wzór jest ciąg, który musiałeś przejść do końca, aby wykonać obrót).

Teraz pytanie brzmi, jak sprawdzić, czy tak jest. W tym celu możemy użyć innego pięknego twierdzenia:

Jeśli x i y są łańcuchami o tej samej długości, to x jest obrotem y wtedy i tylko wtedy, gdy x jest podłańcuchem yy.

Jako przykład widzimy, że loheljest to rotacja w hellonastępujący sposób:

hellohello
   ^^^^^

W naszym przypadku wiemy, że każdy ciąg x zawsze będzie podłańcuchem xx (pojawi się dwa razy, raz w każdej kopii x). Więc po prostu musimy sprawdzić, czy nasz łańcuch x jest podłańcuchem xx, nie pozwalając mu dopasować się do pierwszego lub połowy znaku. Oto jeden wiersz na to:

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

Zakładając, że indexOfjest zaimplementowany przy użyciu algorytmu szybkiego dopasowywania ciągów, będzie to działać w czasie O (n), gdzie n jest długością ciągu wejściowego.

Mam nadzieję że to pomoże!

Możesz to zrobić za pomocą grupy przechwytującej i odwołania wstecznego . Po prostu sprawdź, czy jest to powtórzenie pierwszej przechwyconej wartości.

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

W powyższym RegExp:

1. ^i $oznacza kotwicę początkową i końcową do przewidywania pozycji.
2. (.+)przechwytuje dowolny wzorzec i przechwytuje wartość (z wyjątkiem \n).
3. \1jest odwołaniem wstecznym do pierwszej przechwyconej wartości i \1+sprawdzałby powtórzenie przechwyconej wartości.

Wyjaśnienie Regex tutaj

Do debugowania RegExp użyj: https://regex101.com/r/pqlAuP/1/debugger

Wydajność: https://jsperf.com/reegx-and-loop/13

Być może najszybszym podejściem algorytmicznym jest zbudowanie funkcji Z w czasie liniowym:

Funkcja Z dla tego ciągu jest tablicą o długości n, w której i-ty element jest równy największej liczbie znaków, zaczynając od pozycji i, która pokrywa się z pierwszymi znakami s.

Innymi słowy, z [i] jest długością najdłuższego wspólnego przedrostka między s a sufiksem s zaczynającym się od i.

Implementacja C ++ w celach informacyjnych:

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;
}

Implementacja JavaScript
Dodano optymalizacje - zbudowanie połowy tablicy z i wczesne wyjście

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

Następnie musisz sprawdzić indeksy, iktóre dzielą n. Jeśli znajdziesz takie i, i+z[i]=nto ciąg smożna skompresować do długości ii możesz wrócić true.

Na przykład dla

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

tablica z to

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

i możemy to znaleźć dla

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

więc smoże być reprezentowany jako podciąg o długości 4 powtórzony trzy razy.

Przeczytałem odpowiedź gnasher729 i zaimplementowałem ją. Chodzi o to, że jeśli są jakieś powtórzenia, to musi być (również) pierwsza liczba powtórzeń.

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
}

Nieco inny algorytm to:

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
}

Zaktualizowałem stronę jsPerf, która zawiera algorytmy używane na tej stronie.

Załóżmy, że ciąg S ma długość N i składa się z duplikatów podciągu s, a następnie długość s dzieli N. Na przykład, jeśli S ma długość 15, to podciąg ma długość 1, 3 lub 5.

Niech S będzie wykonane z (p * q) kopii s. Wtedy S jest również zrobione z p kopii (s, powtórzone q razy). Mamy zatem dwa przypadki: Jeśli N jest liczbą pierwszą lub 1, to S można utworzyć tylko z kopii podciągu o długości 1. Jeśli N jest złożona, to wystarczy sprawdzić podciągi s o długości N / p dla liczb pierwszych p dzielących długość S.

Zatem określ N = długość S, a następnie znajdź wszystkie jego czynniki pierwsze w czasie O (sqrt (N)). Jeśli jest tylko jeden czynnik N, sprawdź, czy S jest tym samym łańcuchem powtórzonym N razy, w przeciwnym razie dla każdego czynnika pierwszego p sprawdź, czy S składa się z p powtórzeń pierwszych znaków N / p.

Myślę, że funkcja rekurencyjna może być również bardzo szybka. Pierwszą obserwacją jest to, że maksymalna długość powtarzanego wzoru jest o połowę mniejsza niż długość całego ciągu. Moglibyśmy po prostu przetestować wszystkie możliwe powtarzające się długości wzorów: 1, 2, 3, ..., długość str. / 2

Funkcja rekurencyjna isRepeating (p, str) sprawdza, czy ten wzorzec jest powtarzany w str.

Jeśli str jest dłuższy niż wzorzec, rekurencja wymaga, aby pierwsza część (taka sama długość jak p) była powtórzeniem, a także reszta str. Zatem str jest efektywnie dzielony na kawałki o długości p. Długość.

Jeśli testowany wzorzec i str mają taką samą wielkość, rekursja kończy się tutaj pomyślnie.

Jeśli długość jest inna (dzieje się to dla „aba” i wzorca „ab”) lub jeśli części są różne, zwracane jest fałsz, propagując rekursję.

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

Wydajność: https://jsperf.com/reegx-and-loop/13

Napisałem to w Pythonie. Wiem, że to nie jest platforma, ale zajęło to 30 minut. 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")

Moje podejście jest podobne do gnasher729, ponieważ koncentruje się na potencjalnej długości podciągu, ale jest mniej matematyczne i intensywne:

L: Długość oryginalnego sznurka

S: Potencjalne długości prawidłowych podciągów

Pętla S od (część całkowita) L / 2 do 1. Jeśli L / S jest liczbą całkowitą, sprawdź swój oryginalny ciąg względem pierwszych S znaków oryginalnego ciągu powtórzonych L / S razy.

Powodem tworzenia pętli od L / 2 do tyłu, a nie od 1 w górę, jest uzyskanie największego możliwego podciągu. Jeśli chcesz mieć najmniejszą możliwą pętlę podciągu od 1 do L / 2. Przykład: „abababab” ma zarówno „ab”, jak i „abab” jako możliwe podciągi. Który z nich byłby szybszy, gdybyś dbał tylko o wynik prawda / fałsz, zależy od typu ciągów / podciągów, do których zostanie zastosowany.

Poniższy kod Mathematica prawie wykrywa, czy lista została powtórzona przynajmniej raz. Jeśli ciąg zostanie powtórzony co najmniej raz, zwraca wartość true, ale może również zwrócić wartość true, jeśli łańcuch jest liniową kombinacją powtarzających się ciągów.

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

Ten kod szuka wkładu „pełnej długości”, który w powtarzającym się ciągu musi wynosić zero, ale ciąg accbbdjest również uważany za powtórzony, ponieważ jest sumą dwóch powtarzających się ciągów abababi 012012.

Chodzi o to, aby użyć szybkiej transformaty Fouriera i poszukać widm częstotliwości. Patrząc na inne częstotliwości, powinno być również możliwe wykrycie tego dziwnego scenariusza.

Podstawową ideą tutaj jest zbadanie dowolnego potencjalnego podciągu, zaczynając od długości 1 i kończąc na połowie długości oryginalnego łańcucha. Patrzymy tylko na długości podciągów, które równo dzielą oryginalną długość łańcucha (np. Str.length% substring.length == 0).

Ta implementacja sprawdza pierwszy znak każdej możliwej iteracji podłańcucha przed przejściem do drugiego znaku, co może zaoszczędzić czas, jeśli oczekuje się, że podciągi będą długie. Jeśli po zbadaniu całego podciągu nie zostanie znaleziona żadna niezgodność, zwracamy wartość true.

Zwracamy false, gdy zabraknie nam potencjalnych podciągów do sprawdzenia.

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

Nie jestem zaznajomiony z JavaScriptem, więc nie wiem, jak szybko to będzie, ale tutaj jest liniowe rozwiązanie czasowe (zakładając rozsądną wbudowaną implementację), używając tylko wbudowanych. Opiszę algorytm w pseudokodzie.

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;
}

Pomysł jest podobny do odpowiedzi MBo. Dla każdego, iktóry dzieli długość, strjest powtórzeniem jego pierwszych iznaków wtedy i tylko wtedy, gdy pozostaje taki sam po przesunięciu o iznaki.

Przychodzi mi na myśl, że taka wbudowana funkcja może być niedostępna lub nieefektywna. W takim przypadku zawsze można zaimplementować algorytm KMP ręcznie, co zajmuje mniej więcej taką samą ilość kodu, jak algorytm w odpowiedzi MBo.

Jednym z prostych pomysłów jest zastąpienie łańcucha podłańcuchem „” i jeśli jakikolwiek tekst istnieje, to jest fałszywy, w przeciwnym razie jest prawdziwy.

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