Cod sursa(job #170050)

Utilizator mike4problemsRadu Gabriel mike4problems Data 2 aprilie 2008 12:52:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<cstring>
using namespace std;

#define Max 2000002

char s[Max],w[Max];
int ls,lw,n,h[1000],T[Max];

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void prefix()
{
	int i=2,j=0;
	T[0]=-1,T[1]=0;
	while(i<=lw)
	{
		if(w[i-1]==w[j])
		{
			T[i]=j+1;
			i++,j++;
		}
		else
			if(j>0)
				j=T[j];
			else
				T[i++]=0;
	}
}

void KMP()
{
	prefix();
	int m=0,i=0;
	while(m+i<ls)
	{
		if(w[i]==s[m+i])
		{
			i++;
			if(i==lw)
			{
				if(n<1000)
					h[n]=m;
				n++;
				goto els;
			}
		}
		else 
		{
			els:
			m=m+i-T[i];
			if(i>0) i=T[i];
		}
	}
}

int main()
{
	fin.getline(w,Max);
	fin.getline(s,Max);
	ls=strlen(s);
	lw=strlen(w);
	KMP();
	fout<<n<<'\n';
	n=min(n,1000);
	for(int i=0;i<n;i++)
		fout<<h[i]<<' ';
	fout<<'\n';
}