Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
KMP (Knuth-Morris-Pratt) alqoritmi verilmiş bir modeldə axtarış üçün istifadə olunur sim. Bizə bir S simli və bir p naxışı verilir, məqsədimiz verilən naxışın simdə olub olmadığını müəyyənləşdirməkdir.
Mündəricat
misal
Input:
S = "aaaab"
p = "aab"
Çıxış:
doğru
Sadəlövh yanaşma
Nümunə axtarışı üçün sadəlövh yanaşma verilmiş sətirdə verilən naxış xarakterini xarakterə uyğunlaşdırmaqdır.
misal
S = “aaaab ”-> Maç
p = “aab ”
S = “aaaab ”-> Maç
p = “aab ”
S = “aaaab ”-> Uyğunsuzluq
p = “aab"
S = “aaaab ”-> Maç
p = “aab ”
S = “aaaab ”-> Maç
p = “aab ”
S = "aaaab ”-> Uyğunsuzluq
p = “aab"
S = “aaaab ”-> Maç
p = "aab ”
S = "aaaab ”-> Maç
p = “aab ”
S = "aaaab”-> Maç
p = “aab"
Pattern p, S-də tapılmışdır.
Yuxarıda göstərilən yanaşmada uyğunsuzluqla qarşılaşmaq üçün S String-dəki irəliləyişimizi geri qaytarırıq, buna görə sadəlövh uyğunluq alqoritminin zaman mürəkkəbliyi O (uzunluğu S x uzunluğu p).
KMP alqoritmi
KMP ideyası alqoritm irəliləməni qorumaq və geri qayıtmağı əsas Sətrdə (S) aradan qaldırmaqdır, verilmiş naxış (p) əvvəlcədən işlənərək əldə edilir.
Alqoritm sadəlövh yanaşmaya bənzəyir, xarakter S-də S_də model_p axtarmağa başlayırıq və uyğunsuzluqla qarşılaşırıqsa, əsas S sıraya qayıtmaq əvəzinə, p naxışdakı mövqeyimizi geri qaytarırıq. şəkilçinin nümunənin uyğun hissəsində də bir önək olduğu bir nöqtə.
misal
S = “abcaxabcab ”-> Maç
p = “abcab ”
S = “abcaxabcab ”-> Maç
p = “abkabinə"
S = “abcaxabcab ”-> Maç
p = “abcab ”
S = “abcaxabcab ”-> Maç
p = "abcab ”
S = “abcaxabcab ”-> Uyğunsuzluq
p = “abcab"
Bu nöqtədə s sətrindəki model_p nişanının uyğun hissəsi “abca”, bu 4-cü indeksdəki “a” hissəsində də bir önək olan bir şəkilçi (indeks 1-də “a”) olduğu üçün geri p-ə qayıtdıq. b simvoluna (“a” prefiksinin yanında) və uyğunlaşmağa davam edin.
S = “abcaxabcab ”-> Uyğunsuzluq
p = “abkabinə"
Nümunələrin uyğun hissəsi
S sətirindəki p “a” dır, eyni zamanda bir ön şəkilçi yoxdur, buna görə p-dəki ilk simvola qayıdır və KMP Alqoritmi istifadə edərək uyğunlaşmağa davam edirik.
S = “abcaxabcab ”-> Uyğunsuzluq
p = "abcab ”
Uyğunsuzluq indeks 1-də baş verdi, buna görə String S-də irəlilədik.
S = "abcaxabcab ”(Maç)
p = "abcab ”
S = "abcaxabkabin ”(Maç)
p = “abkabinə"
S = "abcaxabcab ”(Maç)
p = “abcab ”
S = "abcaxabcab ”(Maç)
p = "abcab ”
S = "abcaxabcab”(Maç)
p = “abcab"
S.-də p tapdıq.
Alqoritm
- Cədvəl adlı bir sıra yaradın, ölçüsü, model_p uzunluğuna bərabərdir, cədvəl [i] ən uzun şəkilçinin uzunluğunu saxlayır ki, bu da indeks 1-dən i-ə qədərdir.
- Cədvəlin başlanğıcını başladın [0] = 0, çünki indeks 0 üçün əvvəl də olan şəkilçi yoxdur
- İ = 0 və j = 1 başlanğıcını başladın, j <n (model_p uzunluğu) halında bir döngə edin, 4 və 5-ci addımları təkrarlayın
- P [i] və p [j] uyğun gəlirsə, cədvəl [j] = i + 1, artım i və j
- P [i] və p [j] uyğunsuzluğu və i 0-a bərabər deyilsə, i = cədvəl [i - 1] və i = 0 olarsa, cədvəl [j] = 0 və j artımı
KMP Alqoritmi üçün Pseudo Kodu
table[0] = 0
i = 0, j = 1
while (j < n) { // n is the length of pattern p
if (p[i] == p[j]) {
table[j] = i + 1;
i++;
j++;
} else {
if (i != 0) {
i = table[i - 1];
// Do not increment j here
} else {
table[j] = 0;
j++;
}
}
}
Nümunələr
naxış: “aaab”
cədvəl [] = {0, 1, 2, 0}
naxış: ”dsgwadsgz”
cədvəl = {0, 0, 0, 0, 0, 1, 2, 3, 0}
Alqoritm
- Yuxarıda qeyd edildiyi kimi prefiks-şəkilçi cədvəl seriyası yaratmaq üçün nümunəni əvvəlcədən işləyin.
- Birinci simvoldan başlayaraq verilən simli və naxışları uyğunlaşdırmağa başlayırıq və bütün simvollara uyğun gəlsək, naxış tapılıb dayandıqca simvollarla uyğunlaşana qədər hər iki sətirdə də artmağa davam edirik.
- Bir uyğunsuzluğu gördüyümüz üçün, uyğunsuzluğun nümunədəki i indeksində meydana çıxmasına icazə verin, nümunədəki cədvəl [i - 1] indeksinə və ya uyğunsuzluq 0 indeksində baş verərsə, 0 indeksinə qayıdırıq.
- 2 və 3-cü addımları təkrarlayın, bütün simli keçməyimizə və ya naxışı tapana qədər.
KMP Alqoritmi üçün JAVA Kodu
public class KMPAlgorithm {
// Function to pre-process the pattern and to create the suffix-prefix table
private static void preProcess(char[] p, int[] table, int n) {
// Initialize table[0] as 0
table[0] = 0;
// Initialise i = 0 and j = 1
int i = 0, j = 1;
// Run a loop till length of pattern, if p[i] and p[j] matches table[j] = i + 1 else table[j] = 0
while (j < n) {
if (p[j] == p[i]) {
// Match found set table[i] = i + 1, and advance i and j
table[j] = i + 1;
i++; j++;
} else {
if (i != 0) {
i = table[i - 1];
// We do not increment j here
} else {
table[j] = 0;
j++;
}
}
}
}
public static void main(String[] args) {
char S[] = "abcaabcab".toCharArray();
char p[] = "abcab".toCharArray();
// Pre-process the pattern
int table[] = new int[p.length];
preProcess(p, table, p.length);
// Searching the pattern in the given string
int i = 0; // index for string
int j = 0; // index for pattern
boolean found = false; // Boolean variable to indicate that the pattern is found or not
while (i < S.length) {
if (S[i] == p[j]) {
// Advance forward the characters are same
i++;
j++;
} else {
// Characters are not same, revert back the progress in the pattern
if (j !=0) // Reset the position of j in the pattern, do no advance in string
j = table[j - 1];
else // first character is mis-matched, advance in the string
i++;
}
if (j == p.length) {
// The pattern is found in the string
found = true;
break;
}
}
if (found)
System.out.println("true");
else
System.out.println("false");
}
}
true
KMP alqoritmi üçün C ++ kodu
#include <bits/stdc++.h>
using namespace std;
void preProcess(char *p, int *table, int n) {
// Initialize table[0] as 0
table[0] = 0;
// Initialise i = 0 and j = 1
int i = 0, j = 1;
// Run a loop till length of pattern, if p[i] and p[j] matches table[j] = i + 1 else table[j] = 0
while (j < n) {
if (p[i] == p[j]) {
// Match found set table[i] = i + 1, and advance i and j
table[j] = i + 1;
i++;
j++;
} else {
if (i != 0) {
i = table[i - 1];
// We do not increment j here
} else {
table[j] = 0;
j++;
}
}
}
}
int main() {
char s[] = "abcaabcab";
char p[] = "abcab";
int n = strlen(s);
int m = strlen(p);
// Pre-process the pattern
int table[m];
preProcess(p, table, m);
// Searching the pattern in the given string
int i = 0; // index for string
int j = 0; // index for pattern
bool found = false; // Boolean variable to indicate that the pattern is found or not
while (i < n) {
if (s[i] == p[j]) {
// Advance forward the characters are same
i++;
j++;
} else {
// Characters are not same, revert back the progress in the pattern
if (j != 0) {
// Reset the position of j in the pattern, do no advance in string
j = table[j - 1];
} else {
// first character is mis-matched, advance in the string
i++;
}
}
if (j == m) {
// The pattern is found in the string
found = true;
break;
}
}
if (found)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
return 0;
}
true
KMP Alqoritmi üçün Mürəkkəblik Analizi
KMP alqoritmində S stringində geri qayıtmaq olmur, buna görə zaman mürəkkəbliyi S uzunluğunun sırasıdır və əvvəlcədən işlənmək üçün də model_p uzunluğu ilə mütənasibdir.
Zamanın mürəkkəbliyi = O (String S uzunluğu + Pattern p uzunluğu)
