Cod sursa(job #462588)

Utilizator deneoAdrian Craciun deneo Data 11 iunie 2010 20:43:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<cstring>
using namespace std;
char p[2000001], v[2000001];
int np[2000001], m, n, val[1001];
void prefix()
{
	int i, x=-1;
	np[0]=-1;
	for(i=1; i<=m; ++i)
	{
		while(x>-1 && p[x + 1]!=p[i]) x=np[x];
		if(p[x + 1]==p[i]) 
			x++;
		np[i]=x;
	}
}
int main()
{
	int x=-1, i, nrpos=0, k=0;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(p, 2000000);
	f.getline(v, 2000000);
	n=strlen(v)-1; m=strlen(p)-1;
	prefix();
	for(i=0; i<=n; ++i)
	{
		while(x>-1 && p[x+1]!=v[i])
			x=np[x];
		if(p[x+1]==v[i])
			x++;
		if(x == m)
		{
			x=np[m];
			if(k<=1000)
			{
				val[k]=i-m;
				++k;
			}
			nrpos++;
		}
	}
	g<<nrpos<<'\n';
	for(i=0; i<k; ++i)
		g<<val[i]<<' ';
	g<<'\n';
	g.close();
	return 0;
}