Cod sursa(job #902581)

Utilizator nutipasa16Macovei Claudiu nutipasa16 Data 1 martie 2013 15:13:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<cstring>
#define max_dim 2000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char M[max_dim],N[max_dim];
short n,m,pi[max_dim],nr,sol[max_dim];
void calcul_prefix()
{
	int k;
	k=0; 
	pi[1]=0;
	for(int i=2;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 potrivire_KMP()
{
	int q;
	q=0;
	for(int 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 && nr>1000) 
		{
			nr++;
			sol[nr]=i-n+1;
		}
	}
}
int main()
{
	f>>N>>M;
	n=strlen(N); m=strlen(M);
	for (int i = n; i; --i) M[i] = M[i-1]; M[0] = ' ';     
	for (int i = m; i; --i) N[i] = N[i-1]; N[0] = ' ';
	calcul_prefix();
	potrivire_KMP();
	g<<nr<<'\n';
	for(int i=1;i<=nr;i++)
		g<<sol[i]<<" ";
	g<<'\n';
	return 0;
}