Cod sursa(job #1368645)

Utilizator alevasluialeHuhurez Marius alevasluiale Data 2 martie 2015 19:02:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 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=0,i,nr=0;
    fin.getline(P+1,2000100);
    fin.getline(T+1,2000100);
    int n=strlen(P+1);
    int m=strlen(T+1);
    for(i=2;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=0;
    for(i=1;i<=m;i++)
    {
        while(k>0&&P[k+1]!=T[i])
        {
            k=urm[k];
        }
        if(P[k+1]==T[i]) k++;
        if(k==n)
        {
            nr++;
            if(nr<=1000) v[nr]=i-n;
            k=urm[k];
        }
    }
    fout<<nr<<"\n";
    for(i=1;i<=nr&&i<=1000;i++) fout<<v[i]<<" ";
}