KMP SEARCH

 

1. PREFIX FUNCTION

π(q)=max{k : k < q ;  prefix Pk is a suffix of prefix Pq}

Or sometimes we call π the longest “border” function.

 

2. TRANSITION FUNCTION

We have :

·        If Pq+1=c,  δ(q, c)=q+1;

·        If Pq+1≠c,  δ(q, c) = δ(π(q), c);

 

Meaning: If the current status is q, and we read a character c, then we turn into δ(q, c)

 

3. FINITE AUTOMATION MATCHER

q=0;

for i = 1 to n

            q= δ(q, Si);

            if q = m

                        Find an occurrence of P in S!

 

4. KMP SEARCH

Like doing a finite-automation-matcher, but we compute the transition function right during the search.

 

q=0;

for i = 1 to n

            Compute δ(q, Si); {Using 2}

            q= δ(q, Si);

            if q = m

                        Find an occurrence of P in S!

 

Problem 1423 Timus – String tale:

http://acm.timus.ru/problem.aspx?space=1&num=1423

 

{Do a KMP search T on 2*S}

program _1423;

 

const M=250000;

 

var s, t: array[1..M] of char;

    n: longint;

 

procedure _input;

var i: longint;

begin

     readln(n);

     for i:=1 to n do read(s[i]);

     readln;

     for i:=1 to n do read(t[i]);

end;

 

var p:array[0..M] of longint;

 

procedure calcp; {prefix function}

var i, j: longint;

begin

     p[1]:=0;

     for i:=2 to n do

     begin

          p[i]:=0;

          j:=i-1;

          repeat

               j:=p[j];

               if t[j+1] = t[i] then

               begin

                    p[i]:=j+1;

                    break;

               end;

          until j=0;

     end;

end;

 

var r: longint;

 

procedure kmp;

var i, k, j: longint;

    a: longint;

begin

        a:=0; r:=-1;

        for i:=1 to 2*n do

        begin

                k:=i; if k>n then k:=k-n;

                j:=a;

                repeat

                        if t[j+1]=s[k] then

                        begin

                                a:=j+1;

                                break;

                        end;

                        if j=0 then break;

                        j:=p[j];

                until false;

                if a=n then

                begin

                        r:=2*n-i;

                        if r=n then r:=0;

                        break;

                end;

        end;

end;

 

procedure solve;

begin

     calcp;

     kmp;

end;

 

procedure _output;

begin

     writeln(r);

end;

 

begin

        _input;

        solve;

        _output;

end.