Cod sursa(job #351191)

Utilizator bog29Antohi Bogdan bog29 Data 27 septembrie 2009 11:38:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#define dmax 2000003
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char t[dmax],p[dmax];
int urm[dmax],n,m,ap[1002];

void prefix()
{	int k=0,x;
	urm[1]=0;
	for(x=2;x<=m;x++)
	{	while(k>0 && p[k+1]!=p[x])
			k=urm[k];
		if(p[k+1]==p[x])
			k++;
		urm[x]=k;
	}	
}
int main()
{	int i,x=0,nr=0;
	in.getline(p,dmax,'\n');
	in.getline(t,dmax,'\n');
	in.close();
	n=strlen(t);
	m=strlen(p);
	for(i=n;i>=1;i--)
		t[i]=t[i-1];
	for(i=m;i>=1;i--)
		p[i]=p[i-1];
	prefix();
	for(i=1;i<=n;i++)
	{	while(x>0 && p[x+1]!=t[i])x=urm[x];
		if(p[x+1]==t[i])x++;
		if(x==m)
		{	nr++;
			if(nr<=1000)ap[nr]=i-m;
			x=urm[x];
		}
	}
	out<<nr<<'\n';
	for(i=1;i<=nr && i<=1000;i++)
		out<<ap[i]<<" ";
	out.close();
	return 0;
}