Cod sursa(job #653489)

Utilizator galbenugalbenu dorin galbenu Data 28 decembrie 2011 02:58:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<iostream>
#include<cstring>
#define lmax 2000005
using namespace std;
ifstream f("strmatch.in",fstream::in);
ofstream g("strmatch.out",fstream::out);
char a[lmax],b[lmax];
int n,m,q,i,k,urm[lmax],sol[lmax],nrsol;
void next(char a[])
{   int m,k,q;
    m=strlen(a);
    k=0;
    for(q=2;q<=m;q++)
    {
        while(k && a[k+1]!=a[q])
        k=urm[k];
        if(a[k+1]==a[q])
        k+=1;
        urm[q]=k;
    }
}
int main()
{   f.getline(b+1,lmax);
    f.getline(a+1,lmax);
    n=strlen(a+1);
    m=strlen(b+1);
    next(b+1);
    k=0;
    for(i=1;i<=n;i++)
    {
        while(k && b[k+1]!=a[i])
        k=urm[k];
        if(b[k+1]==a[i])
        k+=1;
        if(k==m-1 && a[i+1]==b[m])
        {
            sol[++nrsol]=i-m+1;
            k=urm[k];
        }
    }
if(nrsol>1000)
nrsol=1000;
g<<nrsol<<"\n";
for(i=1;i<=nrsol;i++)
g<<sol[i]<<" ";
f.close();
g.close();
return 0;
}