Cod sursa(job #555461)

Utilizator bog29Antohi Bogdan bog29 Data 15 martie 2011 15:19:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#define dmax 2000003
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

int n,m,pi[dmax],q,nr, sol[dmax];

char t[dmax], p[dmax];

void prefix()
{	
	int i,k;
	
	pi[1]=0;
	k=0;
	
	for(i=2;i<=m;i++)
	{	
		while( p[i] != p[k+1] && k>0 )
			k=pi[k];
		if(p[i] == p[k+1])
			k++;

		pi[i] = k;
	}
}

int main()
{	
	int i;
	
	in>>p>>t;
	
	in.close();
	
	n=strlen(t);
	m=strlen(p);
	
	for(i=n; i>0 ;i--)
		t[i] = t[i-1];
	for(i=m; i>0 ;i--)
		p[i] = p[i-1];
	
	prefix();
	
	q=0;
	
	for(i=1;i<=n;i++)
	{	
		while(t[i] != p[q+1] && q>0)	
			q = pi[q];
		if(t[i] == p[q+1])
			q++;
		if(q==m)
		{	nr++;
			if(nr <= 1000)
				sol[nr] = i-q;
		}
		
	}
	
	out<<nr<<'\n';
	for(i=1;i<=nr;i++)
		out<<sol[i]<<" ";	
	
	out.close();
	return 0;
}