Cod sursa(job #574469)

Utilizator tinkyAndrei Ilisei tinky Data 7 aprilie 2011 10:57:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
#define nmax 2000010
using namespace std;
//no comment
char a[nmax],b[nmax];
int p[nmax],n,m,sol[1010],s=0;
void citire()
{
	ifstream in("strmatch.in");
	in.getline(a+1,2000005,'\n');
	in.getline(b+1,2000005,'\n');
	m=strlen(a+1);
	n=strlen(b+1);
	a[0]=' ';
	b[0]=' ';	
}

void prefix()
{
	int i,j,k=0;
	for (i=2;i<=m;i++)
	{
		while (k&&a[i]!=a[k+1])
			k=p[k];
		if (a[k+1]==a[i])
			k++;
		p[i]=k;
	}
}
ofstream out("strmatch.out");
void verif()
{
	int i;
	out<<b+1<<'\n';
	out<<a+1<<'\n';
	for (i=1;i<=m;i++)
		out<<p[i]<<"";
}
int main()
{
	int i,j,k=0;
	citire();
	prefix();
	//verif();
	
	for (i=1;i<=n;i++)
	{
		while (k&&a[k+1]!=b[i])
			k=p[k];
		if (a[k+1]==b[i])
			k++;
		if (k==m)
		{
			k=p[m];
			//mem solutie
			s++;
			if (s<=1002)
				sol[s]=i-m+1;
		}
	}
	out<<s<<'\n';
	for (i=1;i<=s&&i<=1000;i++)
		out<<sol[i]-1<<" ";
			
}