Cod sursa(job #1178093)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 26 aprilie 2014 14:25:12
Problema Potrivirea sirurilor Scor 40
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()
{
    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,q=0;i<=n;i++)
    {

        while(q and P[q+1]!=T[i])
            q=v[q];

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

    }
}

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

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

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

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

    return 0;
}