Cod sursa(job #1368600)

Utilizator alevasluialeHuhurez Marius alevasluiale Data 2 martie 2015 18:46:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char P[2000010],T[2000010];
int urm[2000010],v[1001];
int main()
{
    int k=-1,i,nr=0;
    fin.getline(P,2000100);
    fin.getline(T,2000100);
    urm[0]=0;
    for(i=1;P[i]!=0;i++)
    {
        while(k>0&&P[k+1]!=P[i]) k=urm[k];
        if(P[k+1]==P[i]) k++;
        urm[i]=k;
    }
    k=-1;
    for(i=0;T[i]!=0;i++)
    {
        while(k>0&&P[k+1]!=T[i]) k=urm[k];
        if(P[k+1]==T[i]) k++;
        if(P[k+1]==0)
        {
            nr++;
            v[nr]=i-k;
            k=urm[k];
        }
    }
    fout<<nr<<"\n";
    for(i=1;i<=nr&&i<=1000;i++) fout<<v[i]<<" ";
}