KMP

Z RNO-Wiki

Spis treści

Problem wyszukiwania wzorca (WW)

Mamy dane słowo T i wzorzec P. Nasze zadanie polega na tym, żeby znaleźć wszystkie pozycje występowania wzorca P w tekście P. Przy czym mówimy, że wzorzec P występuje na i-tej pozycji, wtedy i tylko wtedy, gdy począwszy od i-tej pozycji, wzorzec "pasuje" do tekstu.

Automaty skończone

Wyszukiwanie wzorca w tekście można realizować za pomocą pewnych automatów skończonych. Oto przykład automatu rozpoznającego w tekscie wzorzec "abaaba" :

Abaaba.gif

Algorytm Knutha-Morrisa-Pratta

Generalnie idea algorytmu jest bardzo prosta. Niech N - długość tekstu, a M - długość wzorca. Problem WW można bardzo prosto rozwiązać sprawdzając dla każdego i, czy kolejne M pozycji się zgadza. Takie sprawdzanie jest jednak bardzo nieefektywne, gdyż dla pesymistycznego przypadku wychodzi nam złożoność rzędu <math>n^2</math>. Taki algorytm nazywany jest algorytmem N ("naiwny"). Można, jednak, taki sam pomysł napisać tak, aby działał liniowo. Zauważmy, że nie trzeba za każdym razem "przesuwać się" w tekście T o jedną pozycję. Czasami możemy zrobić duży skok. To zdecydowanie polepsza złożoność algorytmu. Załóżmy, że mamy policzoną taką tablicę pi, której i-ta wartość określa długość najdłuższego sufixu wzorca, który jest jednocześnie jego prefixem. Dzięki temu wiemy, że gdy na pozycji j występuje niezgodność wzorca z tekstem, możemy j ustawić na pi[j] (dlatego, że na pewno pi[j] pierwszych liter wzorca zgadza się z pi[j] ostatnich liter wzorca) i sprawdzać dalej, pomijając trochę liter.

#include <iostream>
#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
int shift[1000001];
char w[1000001], s[1000001];
int M, N;
 
void init_shifts() // Funkcja generująca przesunięcia, czyli tworząca naszą tablicę pi, zazwaną przeze mnie shifts[]
{
     int i, j;
     shift[0]=-1;
     for (i=0,j=-1; i<M; i++, j++, shift[i]=j)
         while ( (j>=0) && (w[i]!=w[j]) )
               j=shift[j];
}
 
void kmp()
{
    int i=0, j=0;
    N = strlen(s);
    for(i=0; i<=N; i++)
    {
        if(j == M){
            printf("%d\n", i-M);
            j = shift[j];
        }     
        while( (j>=0) && w[j] != s[i])
        {
            j = shift[j];
        }
        j++;
    }
}
 
int main()
{
    int Test;
    scanf("%d\n", &Test); //Test - liczba przypadków testowych.
    while(Test--)
    {
        scanf("%d\n", &M);
        scanf("%s", w);
        scanf("%s", s);
        init_shifts();
        if(M <= strlen(s)) kmp();
 
        memset(s, 0, strlen(s) );
        memset(w, 0, M );
 
        M = N = 0;
        for(int i=1; i<=M; i++) shift[i] = 0;
 
    }
}

Funkcja prefiksowa Knutha

Dla słowa P[0..(m-1)] definiujemy funkcję prefiksową Knutha następująco:

 pi[0] = 0
 pi[k] = długość najdłuższego prefiksu słowa P[0..(k-1)] będącego sufiksem słowa P[1..(k)],  k=1,...,n-1
int   m, k, q, pi[1000001];
char  P[1000001]; // P[] - wzorzec
 
void CPF()
{
	pi[0] = 0; q = 0;
	for(k=1; k<m; k++)
	{
		//niezmiennik: q=pi[k-1]
		while(q>0 && P[k] != P[q])
                        q=pi[q-1];
		if(P[k] == P[q])
                        pi[k] = ++q;
		else      
                	pi[k] = 0;
	}
}

Linki

http://pl.wikipedia.org/wiki/Algorytm_KMP

Osobiste