Cod sursa(job #1178259)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 26 aprilie 2014 14:44:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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];

void prefix()
{
    for(int i=2,k=0;i<=m;i++)
    {
        while(k>0 and P[k+1]!=P[i])
            k=v[k];
        if(P[k+1]==P[i]) 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;
}