Cod sursa(job #546147)

Utilizator judgment7Andrei Aldea judgment7 Data 4 martie 2011 15:20:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
using namespace std;
char p[2000002],s[2000002];
int v[2000002],k,q,m,i,n,a[1005],sol;
void prefix(char p[])
{
	v[1]=0;
	k=0;
	for(q=2;q<=m;q++)
	{
		while(k>0 && p[k+1]!=p[q])
				k=v[k];
		if(p[k+1]==p[q])
			{	k++;
		        v[q]=k;
	         }
		
	}
}
void KMP(char p[],char s[])
{
	prefix(p);
    q=0;
	for(i=1;i<=n;i++)
	{
		while(q>0&&p[q+1]!=s[i])
			q=v[q];
		if(p[q+1]==s[i])
		{	q++;
		  if(q==m)
		    {	sol++;
				if (sol<1001)
					a[sol]=i-q; 

		}    }
	}
}

	


int main()
{ifstream f("strmatch.in");
ofstream g("strmatch.out");
	f.getline(p+1,2000002);
	f.getline(s+1,2000002);
	p[0]=' ';s[0]=' ';
		m=strlen(p)-1;
		n=strlen(s)-1;
	
KMP(p,s);
g<<sol<<"\n";
for(i=1;i<=sol;i++)
	g<<a[i]<<" ";
return 0;
}