Cod sursa(job #1176805)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 26 aprilie 2014 10:56:36
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <string.h>
#include <iostream>

using namespace std;

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

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

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

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

    return j==i+1;
    return false;

}

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


    }
}

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

        q=v[q];
    }
}

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

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

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