Cod sursa(job #1689380)

Utilizator Julian.FMI Caluian Iulian Julian. Data 14 aprilie 2016 10:41:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define nmax 2000099
using namespace std;
char s[nmax],p[nmax];
long n,urm[nmax],sol[nmax],nr;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void pref()
{long i,k;
    urm[0]=-1; k=-1;
    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;
    }


}


int main()
{long  m,x,i;
    fin.getline(p,nmax);
    fin.getline(s,nmax);
    n=strlen(p);
    pref();
    x=-1;

    m=strlen(s);
    for(i=0;i<m;i++)
    {
        while(x>=0 && p[x+1]!=s[i])x=urm[x];
        if(p[x+1]==s[i])x++;
        if(x==n-1)
        {
            sol[++nr]=i-n+1;

            x=urm[x];
        }
        if(nr==1000)break;
    }

    fout<<nr<<endl;
    for(i=1;i<=nr;i++)
        fout<<sol[i]<<' ';
}