KMP alqoritmi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Akkolit Amazon google MakeMyTrip MAQ microsoft Kahin PayU
Nümunə axtarışı SimBaxılıb 135

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.

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"

KMP alqoritmiPin

S.-də p tapdıq.

Alqoritm

  1. 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.
  2. Cədvəlin başlanğıcını başladın [0] = 0, çünki indeks 0 üçün əvvəl də olan şəkilçi yoxdur
  3. İ = 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
  4. P [i] və p [j] uyğun gəlirsə, cədvəl [j] = i + 1, artım i və j
  5. 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

  1. Yuxarıda qeyd edildiyi kimi prefiks-şəkilçi cədvəl seriyası yaratmaq üçün nümunəni əvvəlcədən işləyin.
  2. 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.
  3. 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.
  4. 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)

References

Crack Sistemi Dizayn Müsahibələri
Translate »