Cod sursa(job #559516)

Utilizator tinkyAndrei Ilisei tinky Data 17 martie 2011 21:17:59
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<iostream>
using namespace std;
int v[2000010],sol[2000010];
char a[2000010],b[2000010];
int la,lb,k=0;
void citire()
{
	int i;
	ifstream in("strmatch.in");
	in.getline(a,1000,'\n');
	in.getline(b,1000,'\n');
	la=strlen(a);
	lb=strlen(b);
	for (i=la;i>0;i--)
		a[i]=a[i-1];
	a[0]=' ';
	for (i=lb;i;i--)
		b[i]=b[i-1];
	b[0]=' ';
}
void prefix()
{
	int i,q=0;
	for (i=2,v[i]=0;i<=la;i++)
	{
		while (q&&a[q+1]!=a[i])
			q=v[q];
		if (a[q+1]==a[i])
			++q;
		v[i]=q;
	}
}

void kmp()
{
	int i,q=0;
	for (i=1;i<=lb;i++)
	{
		while (q&&a[q+1]!=b[i])
			q=v[q];
		if (a[q+1]==b[i])
			q++;
		if (q==la)
		{
			k++;
			if (k<=1000)
				sol[k]=i-la;
		}
	}
}
int main()
{
	int i,j;
	citire();
	prefix();
	kmp();
	ofstream out("strmatch.out");
	out<<k<<'\n';
	k=min(k,1000);
	for (i=1;i<=k;i++)
		out<<sol[i]<<" ";
	out<<'\n';
	/*for (i=1;i<=la+1;i++)
		cout<<v[i]<<" ";*/
	
}