Cod sursa(job #1178142)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 26 aprilie 2014 14:31:20
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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';
    if(l<=1000)
    {
        for(int i=1;i<=l;i++)
            tata<<x[i]<<" ";
    }
    else
    {
        for(int i=1;i<=1000;i++)
            tata<<x[i]<<" ";
    }
    return 0;
}