Untuk menyelesaikan masalah ini, penghitungan biasa tidak akan berfungsi, kerana asimptotiknya ialah
O(t*s). Oleh itu, untuk tugas carian subrentetan, algoritma KMP (Knuth-Morris-Pratt) digunakan.
Untuk melaksanakan algoritma ini, fungsi awalan rentetan digunakan, ini ialah tatasusunan nombor panjang
n (strong>s panjang), di mana setiap elemen ialah panjang maksimum daripada akhiran terbesar sendiri bagi subrentetan
s, padanan dengan awalannya. Contohnya:
| Barisan |
Fungsi awalan |
Nota |
| abababcab |
0 0 1 2 3 4 0 1 2 |
|
| abcabcd |
0 0 0 1 2 3 0 |
|
| aabaaab |
0 1 0 1 2 2 3 |
|
Algoritma fungsi awalan remeh dengan asimptotik O(n^3):
vektor<int> prefix_function (rentetan s) {
int n = (int ) s.length();
vektor<int>pi(n);
untuk (int i=0; i<n; ++i)
untuk (int k=0; k<=i; ++k)
jika (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
kembalipi;
}
Dan sekarang kita perlu membuat fungsi awalan untuk rentetan bentuk: & nbsp; t + # + s, dengan # ialah aksara pembatas yang jelas tiada dalam teks. Menganalisis nilai-nilai fungsi awalan selepas aksara pemisah yang sepadan, perlu diperhatikan bahawa jika nilai yang terhasil adalah sama dengan panjang subrentetan yang dikehendaki, maka kejadiannya dijumpai. Contohnya, untuk rentetan "abababcab" dan subrentetan yang dikehendaki "abab", fungsi awalan ialah:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 kita perlu menghuraikan unsur-unsur rentetan yang sepadan s:
1 2 3 4 3 4 0 1 2 - terdapat dua kes di mana nilainya ialah 4 ( ke-4 dan ke-6 ), i.e. panjang t, akibatnya, jawapan mesti ditulis: 4 - 4 (panjang t) & nbsp; = 0 dan 6 - 4 = 2. Dapat dilihat bahawa ini adalah jawapan yang betul dan rentetan "abab" sebenarnya adalah subrentetan dalam rentetan "abababcab" dalam kedudukan 0 dan 2.
Selepas mengoptimumkan fungsi awalan (untuk butiran di sini ), kami mendapat algoritma akhir dengan asimptotik O(n):
vektor<int> prefix_function (rentetan s) {
int n = (int ) s.length();
vektor<int>pi(n);
untuk (int i=1; i<n; ++i) {
int j = pi[i-1< /span>];
sementara (j > 0 && s[i] != s[j])
j = pi[j-1];
jika (s[i] == s[j]) ++j;
pi[i] = j;
}
kembalipi;
}
|
Z-function
Z-function daripada rentetan S - tatasusunan Z, setiap elemen ialah Z [i ] adalah sama dengan awalan terpanjang subrentetan bermula pada kedudukan i dalam rentetan S, yang juga merupakan awalan keseluruhan rentetan Z. Nilai fungsi Z-pada kedudukan sifar biasanya sama ada sifar atau panjang keseluruhan rentetan.
Kesukaran
O(|S| ^ 2) atau O(|S|).
Fungsi awalan daripada rentetan S - tatasusunan P, setiap elemen yang P[i] adalah sama dengan akhiran terpanjang bagi subrentetan bermula dari kedudukan < code>i dalam rentetan S, yang juga merupakan akhiran keseluruhan rentetan S. Nilai P-fungsi pada kedudukan sifar biasanya sama ada sifar atau panjang keseluruhan rentetan.
Kesukaran
O(|S| ^ 2) atau O(|S|).
Cuba laksanakan Fungsi Z dan fungsi awalan untuk O(|S| ^ 2) .
|
Kedua-dua Z dan awalan fungsi boleh digunakan untuk melaksanakan algoritma KMP(Knuth-Morris-Pratt) untuk mencari subrentetan dalam rentetan dalam O(|S|). Intipati algoritma ini adalah seperti berikut: kami mengaitkan kepada rentetan yang kami mahu mencari rentetan yang kami cari. Adalah sangat diingini untuk meletakkan aksara pemisah antara baris ini, iaitu aksara yang tidak berlaku dalam mana-mana baris (biasanya #).
|