Cod sursa(job #825741)

Utilizator raulstoinStoin Raul raulstoin Data 29 noiembrie 2012 14:56:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<string.h>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax],b[nmax];
int p[nmax],poz[1005],k,n,m;
void prefix()
{
	for(int i=2,q=0;i<=m;i++)
	{
		while(q && a[q+1]!=a[i])
			q=p[q];
		if(a[q+1]==a[i])
			q++;
		p[i]=q;
	}
}
void kmp()
{
	for(int i=1,q=0;i<=n;i++)
	{
		while(q && a[q+1]!=b[i])
			q=p[q];
		if(a[q+1]==b[i])
			q++;
		if(q==m)
		{
			q=p[m];
			k++;
			if(k<=1000)
				poz[k]=i-m;
		}
	}
}
void afisare()
{
	int i;
	g<<k<<'\n';
	if(k>1000)
		k=1000;
	for(i=1;i<=k;i++)
		g<<poz[i]<<' ';
	g<<'\n';
	g.close();
}
void citire()
{
	a[0]=b[0]=' ';
	f>>a+1>>b+1;
	m=strlen(a)-1;
	n=strlen(b)-1;
	f.close();
}
int main()
{
	citire();
	prefix();
	kmp();
	afisare();
	return 0;
}