Cod sursa(job #350741)

Utilizator bog29Antohi Bogdan bog29 Data 25 septembrie 2009 18:54:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#define dmax 2000003
#define dmax2 1003
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char t[dmax],p[dmax];
long int n,m,urm[dmax],sol[dmax2];
void geturm()
{	long int i,k=-1;
	urm[0]=0;
	for(i=1;i<m;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 int i,x=-1;
	in.getline(p,dmax,'\n');
	in.getline(t,dmax,'\n');
	in.close();
	n=strlen(t);
	m=strlen(p);
	geturm();
	for(i=0;i<n;i++)
	{	while(x>0 && t[i]!=p[x+1])
			x=urm[x];
		if(t[i]==p[x+1])
			x++;
		if(x==m-1)
		{	sol[0]++;
			sol[sol[0]]=i-m+1;
			x=urm[x];
		}
	}
	out<<sol[0]<<'\n';
	for(i=1;i<=sol[0]&&i<=1000;i++)
		out<<sol[i]<<" ";	
	out.close();
	return 0;
}