Cod sursa(job #1368611)

Utilizator alevasluialeHuhurez Marius alevasluiale Data 2 martie 2015 18:49:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstring>
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);
    int n=strlen(P);
    int m=strlen(T);
    urm[0]=0;
    for(i=1;i<n;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;i<m;i++)
    {
        while(k>0&&P[k+1]!=T[i]) k=urm[k];
        if(P[k+1]==T[i]) k++;
        if(k==n-1)
        {
            nr++;
            v[nr]=i-n+1;
            k=urm[k];
        }
    }
    fout<<nr<<"\n";
    for(i=1;i<=nr&&i<=1000;i++) fout<<v[i]<<" ";
}