Cod sursa(job #1177562)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 26 aprilie 2014 12:54:48
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <string>
#include <iostream>

using namespace std;

ifstream mama("strmatch.in");
ofstream tata("strmatch.out");

string P,T;
int n,m,l,v[2000001],x[2000001];

bool sufix(int k, int i)
{
    int j=i-k+1, r=1;

    while(j<=i and P[j]==P[r])
    {
        r++;
        j++;
    }

    return j==i+1;
}

void prefix()
{
    v[0]=0;
    v[1]=0;
    for(int i=2,k;i<=m;i++)
    {
        k=i-1;
        while(!sufix(k,i) and k>0)
            k--;
        v[i]=k;

    }
}

void KMP()
{
    prefix();
    for(int i=1,ok=0,q=0;i<=n;i++)
    {
        ok=0;
        while(q<m and P[q+1]==T[i])
        {
            ok=1;
            q++;
            i++;
        }

        if(ok) i--;
        if(q==m) if(l<1000) { l++; x[l]=i-m;}
        q=v[q];
    }
}

int main()
{
    mama>>P>>T;

    m=P.size();
    n=T.size();

    P=" "+ P;
    T=" "+ T;

    KMP();

    tata<<l<<'\n';
    for(int i=1;i<=l;i++)
        tata<<x[i]<<" ";

    return 0;
}