Cod sursa(job #446920)

Utilizator siminescuPaval Cristi Onisim siminescu Data 26 aprilie 2010 21:16:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
using namespace std;
#define nmax 2000001
char A[nmax],B[nmax];
int L[nmax],poz[1001],pozz,a,b;
void prefix()
{
	int k,p;
	L[1]=0;
	for(p=2;p<=a;p++)
	{
		k=L[p-1];
		while(k>0 && A[k+1]!=A[p]) k=L[k];
		if(A[k+1]==A[p]) k++;
		L[p]=k;
	}
}
void KMP()
{
	int k=0,t;
	for(t=1;t<=b;t++)
	{
		while(k>0 && A[k+1]!=B[t]) k=L[k];
		if(A[k+1]==B[t]) k++;
		if(k==a)
		{
			pozz++;
			if(pozz<1001) poz[pozz]=t-a;
			k=L[k];
		}
	}
}
int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(A+1,nmax,'\n');a=strlen(A+1);
	f.getline(B+1,nmax,'\n');b=strlen(B+1);
	prefix();KMP();g<<pozz<<'\n';
	if(pozz>1000) pozz=1000;
	for(int i=1;i<=pozz;i++) g<<poz[i]<<" ";
}