Cod sursa(job #278499)

Utilizator FllorynMitu Florin Danut Flloryn Data 12 martie 2009 12:52:12
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#include<string.h>

using namespace std;

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

char n[2000001],m[2000001];
long N,M;
long pi[2000001],x[1005],c;

void pref()
{   long i,k;
	k=0;
	for(i=2,pi[1]=0;i<=N;i++)
	{	while(k>0&&n[k+1]!=n[i])
			k=pi[k];
		if(n[k+1]==n[i])
			k++;
		pi[i]=k;
	}
}

void kmp()
{   long q,i;
	q=0;
	pref();
	for(i=1;i<=M;i++)
	{	while(q>0&&n[q+1]!=m[i])
			q=pi[q];
		if(n[q+1]==m[i])
			q++;
		if(q==N)
		{	c++;
			q=pi[N];
			if(c<=1000)
			   x[c]=i-N;
		}
	}
}

int main()
{   fin>>n>>m;
    long i;
    M=strlen(m);
    N=strlen(n);
    for(i=N;i>=0;i--)
       n[i]=n[i-1];
    n[0]=' ';
    for(i=M;i>=0;i--)
        m[i]=m[i-1];
    m[0]=' ';
	kmp();
	fout<<c<<" \n";
	if(c>1000) c=1000;
	for(i=1;i<=c;i++)
           fout<<x[i]<<" ";
    fin.close();
    fout.close();
	return 0;
}