Cod sursa(job #1166194)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 3 aprilie 2014 12:48:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
#include<string.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n,m,st[2000010],sol[1010],str,p,i;
char a[2000010],b[2000010];

int main()
{
    fin>>(a+1);fin>>(b+1);
    n=strlen(a+1);m=strlen(b+1);
    for(i=2;i<=n;i++)
    {
        while(p && a[i]!=a[p+1])p=st[p];
        if(a[i]==a[p+1])p++;
        st[i]=p;
    }
    for(p=0,i=1;i<=m;i++)
    {
        while(p && b[i]!=a[p+1])p=st[p];
        if(b[i]==a[p+1])p++;
        if(p==n)
        {
            str++;
            if(str<=1000) sol[str]=i-n;
        }
    }
    fout<<str<<"\n";
    if(1000<str)str=1000;
    for(i=1;i<=str;i++)fout<<sol[i]<<' ';
    return 0;
}