Bagaimana cara memeriksa apakah string seluruhnya terbuat dari substring yang sama?

Saya harus membuat fungsi yang mengambil string, dan itu harus kembali trueatau falsedidasarkan pada apakah input terdiri dari urutan karakter yang diulang. Panjang string yang diberikan selalu lebih besar dari 1dan urutan karakter harus memiliki setidaknya satu pengulangan.

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

Saya telah membuat fungsi di bawah ini:

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

Memeriksa ini adalah bagian dari masalah sebenarnya. Saya tidak mampu membeli solusi yang tidak efisien seperti ini. Pertama-tama, ia berputar melalui setengah dari string.

Masalah kedua adalah bahwa ia menggunakan replace()di setiap loop yang membuatnya lambat. Apakah ada solusi yang lebih baik mengenai kinerja?

Ada teorema kecil yang bagus tentang string seperti ini.

Sebuah string terdiri dari pola yang sama berulang beberapa kali jika dan hanya jika string itu adalah rotasi nontrivial itu sendiri.

Di sini, rotasi berarti menghapus sejumlah karakter dari depan string dan memindahkannya ke belakang. Misalnya, string hellodapat diputar untuk membentuk salah satu dari string ini:

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

Untuk melihat mengapa ini bekerja, pertama, asumsikan bahwa suatu string terdiri dari k salinan berulang dari string w. Kemudian menghapus salinan pertama dari pola yang berulang (w) dari depan string dan menempelkannya ke belakang akan mengembalikan string yang sama. Arah sebaliknya agak sulit untuk dibuktikan, tetapi idenya adalah bahwa jika Anda memutar string dan mendapatkan kembali apa yang Anda mulai, Anda dapat menerapkan rotasi itu berulang kali untuk memasang string dengan beberapa salinan dari pola yang sama (pola yang menjadi string yang Anda butuhkan untuk pindah ke ujung untuk melakukan rotasi).

Sekarang pertanyaannya adalah bagaimana memeriksa apakah ini masalahnya. Untuk itu, ada teorema indah lain yang bisa kita gunakan:

Jika x dan y adalah string dengan panjang yang sama, maka x adalah rotasi y jika dan hanya jika x adalah substring dari yy.

Sebagai contoh, kita dapat melihat bahwa itu loheladalah rotasi hellosebagai berikut:

hellohello
   ^^^^^

Dalam kasus kami, kami tahu bahwa setiap string x akan selalu menjadi substring dari xx (itu akan muncul dua kali, sekali pada setiap salinan x). Jadi pada dasarnya kita hanya perlu memeriksa apakah string x adalah substring dari xx tanpa membiarkannya cocok dengan karakter pertama atau setengah. Berikut ini satu kalimat untuk itu:

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

Dengan asumsi indexOfdiimplementasikan menggunakan algoritma pencocokan string cepat, ini akan berjalan dalam waktu O (n), di mana n adalah panjang dari string input.

Semoga ini membantu!

Anda dapat melakukannya dengan menangkap grup dan referensi kembali . Periksa saja pengulangan dari nilai yang ditangkap pertama.

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

Di RegExp di atas:

1. ^dan $singkatan dari awal dan akhir jangkar untuk memprediksi posisi.
2. (.+)menangkap pola apa pun dan menangkap nilai (kecuali \n).
3. \1adalah referensi balik dari nilai yang ditangkap pertama dan \1+akan memeriksa pengulangan nilai yang ditangkap.

Penjelasan regex di sini

Untuk penggunaan debug RegExp: https://regex101.com/r/pqlAuP/1/debugger

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

Mungkin pendekatan algoritmik tercepat adalah membangun fungsi-Z dalam waktu linier:

Fungsi-Z untuk string ini adalah array dengan panjang n di mana elemen ke-i sama dengan jumlah karakter terbesar dimulai dari posisi i yang bertepatan dengan karakter pertama dari s.

Dengan kata lain, z [i] adalah panjang awalan umum terpanjang antara s dan akhiran s mulai dari i.

Implementasi C ++ untuk referensi:

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

Implementasi JavaScript
Menambahkan optimasi - membangun setengah z-array dan keluar awal

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

Maka Anda perlu memeriksa indeks iyang membagi n. Jika Anda menemukan iitu i+z[i]=nmaka string sdapat dikompresi dengan panjang idan Anda dapat kembali true.

Misalnya, untuk

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

z-array adalah

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

dan kita dapat menemukannya untuk

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

jadi smungkin direpresentasikan sebagai substring dengan panjang 4 diulang tiga kali.

Saya membaca jawaban gnasher729 dan mengimplementasikannya. Idenya adalah bahwa jika ada pengulangan, maka harus ada (juga) jumlah pengulangan utama.

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
}

Algoritma yang sedikit berbeda adalah ini:

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
}

Saya telah memperbarui halaman jsPerf yang berisi algoritma yang digunakan pada halaman ini.

Asumsikan string S memiliki panjang N dan terbuat dari duplikat substring s, maka panjang s membagi N. Misalnya, jika S memiliki panjang 15, maka substring memiliki panjang 1, 3, atau 5.

Biarkan S dibuat dari (p * q) salinan s. Kemudian S juga terbuat dari salinan p (s, diulang q kali). Karena itu kami memiliki dua kasus: Jika N adalah prima atau 1, maka S hanya dapat dibuat dari salinan panjang substring 1. Jika N adalah komposit, maka kita hanya perlu memeriksa substring s dengan panjang N / p untuk primes p membagi panjang S.

Jadi tentukan N = panjang S, lalu temukan semua faktor prima dalam waktu O (sqrt (N)). Jika hanya ada satu faktor N, periksa apakah S adalah string yang sama diulang N kali, jika tidak untuk setiap faktor prima p, periksa apakah S terdiri dari p pengulangan karakter N / p pertama.

Saya pikir fungsi rekursif mungkin sangat cepat juga. Pengamatan pertama adalah bahwa panjang pola maksimum yang diulang adalah setengah panjang total string. Dan kita bisa menguji semua kemungkinan panjang pola yang berulang: 1, 2, 3, ..., str.length / 2

Fungsi rekursif isRepeating (p, str) menguji jika pola ini diulang dalam str.

Jika str lebih panjang dari pola, rekursi membutuhkan bagian pertama (panjang yang sama dengan p) untuk menjadi pengulangan serta sisa str. Jadi str secara efektif dipecah menjadi potongan-potongan panjang p.length.

Jika pola dan str yang diuji memiliki ukuran yang sama, rekursi berakhir di sini, berhasil.

Jika panjangnya berbeda (terjadi untuk "aba" dan pola "ab") atau jika potongannya berbeda, maka false dikembalikan, menyebarkan rekursi.

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

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

Tulis ini dalam Python. Saya tahu itu bukan platform, tetapi butuh waktu 30 menit. 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")

Pendekatan saya mirip dengan gnasher729, karena menggunakan panjang potensial substring sebagai fokus utama, tetapi kurang matematika-y dan proses intensif:

L: Panjang string asli

S: Panjang potensial dari sub-string yang valid

Loop S dari (bagian integer) L / 2 ke 1. Jika L / S adalah integer, periksa string asli Anda terhadap karakter S fist dari string asli yang diulangi kali L / S.

Alasan untuk pengulangan dari L / 2 mundur dan tidak dari 1 dan seterusnya adalah untuk mendapatkan substring terbesar. Jika Anda ingin loop substring sekecil mungkin dari 1 hingga L / 2. Contoh: "abababab" memiliki "ab" dan "abab" sebanyak mungkin substring. Manakah dari keduanya akan lebih cepat jika Anda hanya peduli tentang hasil benar / salah tergantung pada jenis string / substring ini akan diterapkan.

Kode Mathematica berikut hampir mendeteksi jika daftar diulang setidaknya sekali. Jika string diulang setidaknya satu kali, ia mengembalikan nilai true, tetapi mungkin juga mengembalikan nilai true jika string adalah kombinasi linear dari string yang berulang.

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

Kode ini mencari kontribusi "full-length", yang harus nol dalam string berulang, tetapi string accbbdjuga dianggap diulang, karena merupakan jumlah dari dua string berulang abababdan 012012.

Idenya adalah menggunakan Fast Fourier Transform, dan mencari spektrum frekuensi. Dengan melihat frekuensi lain, seseorang seharusnya dapat mendeteksi skenario aneh ini juga.

Ide dasar di sini adalah untuk memeriksa setiap substring potensial, mulai dari panjang 1 dan berhenti di setengah dari panjang string asli. Kami hanya melihat panjang substring yang membagi panjang string asli secara merata (mis. Str.length% substring.length == 0).

Implementasi ini melihat karakter pertama dari setiap kemungkinan pengulangan substring sebelum pindah ke karakter kedua, yang mungkin menghemat waktu jika substring diharapkan panjang. Jika tidak ada ketidakcocokan yang ditemukan setelah memeriksa seluruh substring, maka kami mengembalikan true.

Kami mengembalikan false ketika kami kehabisan substring potensial untuk memeriksa.

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

Saya tidak terbiasa dengan JavaScript, jadi saya tidak tahu seberapa cepat ini akan terjadi, tapi di sini adalah solusi waktu linier (dengan asumsi implementasi builtin yang masuk akal) hanya menggunakan builtin. Saya akan menjelaskan algoritma dalam pseudocode.

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

Idenya mirip dengan jawaban MBo. Untuk setiap iyang membagi panjang, stradalah pengulangan ikarakter pertama jika dan hanya jika tetap sama setelah beralih untuk ikarakter.

Terlintas dalam pikiran saya bahwa builtin seperti itu mungkin tidak tersedia atau tidak efisien. Dalam hal ini, selalu dimungkinkan untuk mengimplementasikan algoritma KMP secara manual, yang membutuhkan jumlah kode yang sama dengan algoritma dalam jawaban MBo.

Salah satu ide sederhana adalah mengganti string dengan substring "" dan jika ada teks maka itu salah, kalau tidak itu benar.

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