Cod sursa(job #1689410)

Utilizator Julian.FMI Caluian Iulian Julian. Data 14 aprilie 2016 11:01:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define nmax 2000999
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)
        {
            if(nr<1000)
            sol[++nr]=i-n+1;
            else nr++;
            x=urm[x];
        }

    }

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