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 7: Linia 7:
 
Oto przykład automatu rozpoznającego w tekscie wzorzec "abaaba" :
 
Oto przykład automatu rozpoznającego w tekscie wzorzec "abaaba" :
 
[[Grafika:Abaaba.gif|190 px|right]]
 
[[Grafika:Abaaba.gif|190 px|right]]
 +
 +
== 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
 +
 +
<source lang="cpp">
 +
int  m, k, q, pi[1000001];
 +
char  P[1000001]; // P[] - wzorzec o dlugosci m
 +
 +
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;
 +
        }
 +
}
 +
</source>
  
 
== Algorytm Knutha-Morrisa-Pratta ==
 
== Algorytm Knutha-Morrisa-Pratta ==
Linia 13: Linia 40:
 
Poniższy program rozwiązuje zadanie [http://www.spoj.pl/problems/KMP/]
 
Poniższy program rozwiązuje zadanie [http://www.spoj.pl/problems/KMP/]
 
<source lang="cpp">
 
<source lang="cpp">
#include <iostream>
 
 
#include <cstdio>
 
#include <cstdio>
#include <cstdlib>
+
#include <string>
  
 
using namespace std;
 
using namespace std;
Linia 63: Linia 89:
 
     {
 
     {
 
         scanf("%d\n", &m);
 
         scanf("%d\n", &m);
         scanf("%s", P); m = strlen(P);
+
         scanf("%s", P); // m = strlen(P);
//       scanf("%d\n", &n);
+
//     scanf("%d\n", &n);
 
         scanf("%s", T); n = strlen(T);
 
         scanf("%s", T); n = strlen(T);
 
         CPF();
 
         CPF();
Linia 70: Linia 96:
 
     }
 
     }
 
     return 0;
 
     return 0;
}
 
</source>
 
 
== 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
 
 
<source lang="cpp">
 
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;
 
}
 
 
}
 
}
 
</source>
 
</source>

Wersja z 10:24, 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

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 o dlugosci m
 
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;
        }
}

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 <cstdio>
#include <string>
 
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;
}

Linki

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

Osobiste