Znajdowanie Szablonu Z Uzyciem Kmp

Problem znajdowania szablonu dla slowa v można sprowadzić do problemu znajdowania takiego najkrótszego słowa u bedacego jego prefixo-sufiksem, którym można pokryć całe słowo v tj. w taki sposób żeby pomiedzy kolejnymi wystapieniami wzorca nie było odstepow i zeby pokrywaly w sumie cały tekst (poszczególne wystąpienia mogą zachodzić na siebie). Pierwszym pomyslem jaki nam przychodzi jest sprawdzenie kazdego prefixo-sufixu u czy mozna nim pokryc caly tekst, np. za pomocą algorytmu KMP. Taki algorytm miałby złozonosc O(n^2), czyli za dużą. Można jednak zmniejszyć złozonosc eliminując te prefixo-sufixy, które napewno nie będą naszym szablonem. W ten sposób otrzymujemy algorytm o złożoności O(n log n).

string napis; //to nasz tekst
 
int lenght; //dlugosc naszego tekstu
 
int pi[MAX_LEN+1]; //tablica funkcji prefixowej
 
vector<int> prefosufs; //tablica prefikso-sufiksow
 
void knuth_pi(){ //wypelniamy tablice prefikowa dla napisu
 
        int j=0;
 
        pi[0] = pi[1] = 0;
 
        for(int i=2; i<=lenght; ++i){
 
                while(j>0 && napis[j]!=napis[i-1])j=pi[j];
 
                if(napis[j]==napis[i-1])j++;
 
                pi[i]=j;
        }
}
 
bool kmp_matched(int n){ //sprawdzamy za pomoca zmienionego algorytmu KMP czy można pokryc danym pref-sufem caly tekst
 
    int i=0, j=0;
    int last=-1;
 
    while(i+n<=lenght){
 
        if(last+1<i)return false; //natrafiono na odstęp pomiędzy wystąpieniami wzorca  
 
        while(j < n && napis[j]==napis[i + j])j++;
 
        if(j==n)last=i+n-1; //kolejne wystapienie wzorca
 
        i+=max(1, j-pi[j]);
 
        j=pi[j];
    }
    return true; //pokryto cały tekst
}
 
void pref_suf(){ //wypelniamy tablice prefikso-sufiksow na podstawie tablicy funkcji prefiksowej
 
    int i = lenght;
 
    prefosufs.clear();
 
    while (i>0){
 
          prefosufs.push_back(i);
 
          i=pi[i];
        }
}
 
void presito(){ //usuwamy te prefikso-sufiksy ktore napewno nie beda naszym szablonem
 
    vector<int> tmp; 
 
    for (int i = 1; i < (int) prefosufs.size(); ++i)if (2 * prefosufs[i] < prefosufs[i - 1])tmp.push_back(prefosufs[i - 1]);    
 
        tmp.push_back(prefosufs[prefosufs.size() - 1]);
 
        prefosufs = tmp;
}
int main(){
 
    cin>>napis;
 
    lenght=napis.size();
 
    knuth_pi(); //obliczamy funkcje prefixowa
 
    pref_suf(); //wypelniamy tablice prefikso-sufiksow
 
    presito(); //usuwamy te co do ktorych jestesmy pewni ze nie beda szablonem (bez tej linijki złosonosc kwadratowa)
 
    int it=prefosufs.size();
 
    while(!kmp_matched(prefosufs[--it])); //sprawdzamy wszystkie pozostałe prefikso-sufiksy od najkrótszych az znajdziemy odpowiedni lub gdy dojdziemy do calego tekstu
 
    cout<<prefosufs[it]; //wypisuje dlugosc najkrotszego prefikso-sufiksu pokrywajacego caly tekst
 
    return 0;
}
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License