KMP

Z RNO-Wiki
(Różnice między wersjami)
(Algorytm Knutha-Morrisa-Pratta: ; Musiałem to poprawić, bo było strasznie zagmatwane; po pierwsze M i N, zamiast m i n; po drugie w i s zamiast P i T; shift zamiast pi ; shift był przesunięty)
Linia 11: Linia 11:
 
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.
 
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.
  
 +
Poniższy program rozwiązuje zadanie [http://www.spoj.pl/problems/KMP/]
 
<source lang="cpp">
 
<source lang="cpp">
 
#include <iostream>
 
#include <iostream>
Linia 18: Linia 19:
 
using namespace std;
 
using namespace std;
  
int shift[1000001];
+
int   n, m, k, q, pi[1000001];
char w[1000001], s[1000001];
+
char P[1000001]; // P[] - wzorzec o dlugosci m
int M, N;
+
char  T[1000001]; // T[] - tekst o dlugosci n
  
void init_shifts() // Funkcja generująca przesunięcia, czyli tworząca naszą tablicę pi
+
void CPF() // obliczanie funkcji prefiksowej Knutha
                  // nazwaną przeze mnie shifts[]
+
 
{
 
{
    int i, j;
+
        // m = strlen(P);
    shift[0]=-1;
+
        pi[0] = 0; q = 0;
    for (i=0,j=-1; i<M; i++, j++, shift[i]=j)
+
        for(k=1; k<m; k++)
        while ( (j>=0) && (w[i]!=w[j]) )
+
        {
              j=shift[j];
+
                //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;
 +
        }
 
}
 
}
  
 
void kmp()
 
void kmp()
 
{
 
{
     int i=0, j=0;
+
     int q=0;
     N = strlen(s);
+
     //  n = strlen(s);
     for(i=0; i<=N; i++)
+
     for(int i=0; i<n; i++)
 
     {
 
     {
         if(j == M){
+
         while(q>0 && T[i] != P[q]) q = pi[q-1];
            printf("%d\n", i-M);
+
         if (T[i] == P[q]) q++;
            j = shift[j];
+
        if(q == m)
         }   
+
        while( (j>=0) && w[j] != s[i])
+
 
         {
 
         {
             j = shift[j];
+
             // znaleziono wzorzec !!!
 +
            printf("%d\n", i-m + 1); // plus jeden
 +
            q = pi[q-1];
 
         }
 
         }
        j++;
 
 
     }
 
     }
 
}
 
}
Linia 56: Linia 62:
 
     while(Test--)
 
     while(Test--)
 
     {
 
     {
         scanf("%d\n", &M);
+
         scanf("%d\n", &m);
         scanf("%s", w);
+
         scanf("%s", P); m = strlen(P);
        scanf("%s", s);
+
//        scanf("%d\n", &n);
         init_shifts();
+
         scanf("%s", T); n = strlen(T);
        if(M <= strlen(s)) kmp();
+
         CPF();
          
+
         if(m <= n) kmp();
        memset(s, 0, strlen(s) );
+
         memset(w, 0, M );
+
       
+
        M = N = 0;
+
        for(int i=1; i<=M; i++) shift[i] = 0;
+
       
+
 
     }
 
     }
 
     return 0;
 
     return 0;
 
}
 
}
 
 
</source>
 
</source>
  

Wersja z 10:20, 5 lut 2008

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.

Poniższy program rozwiązuje zadanie [1]

#include <iostream>
#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
int   n, m, k, q, pi[1000001];
char  P[1000001]; // P[] - wzorzec o dlugosci m
char  T[1000001]; // T[] - tekst o dlugosci n
 
void CPF() // obliczanie funkcji prefiksowej Knutha
{
        // m = strlen(P);
        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;
        }
}
 
void kmp()
{
    int q=0;
    //  n = strlen(s);
    for(int i=0; i<n; i++)
    {
        while(q>0 && T[i] != P[q]) q = pi[q-1];
        if (T[i] == P[q]) q++;
        if(q == m)
        {
            // znaleziono wzorzec !!!
            printf("%d\n", i-m + 1); // plus jeden
            q = pi[q-1];
        }
    }
}
 
int main()
{
    int Test;
    scanf("%d\n", &Test); //Test - liczba przypadków testowych.
    while(Test--)
    {
        scanf("%d\n", &m);
        scanf("%s", P); m = strlen(P);
//        scanf("%d\n", &n);
        scanf("%s", T); n = strlen(T);
        CPF();
        if(m <= n) kmp();
    }
    return 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