Cod sursa(job #300492)

Utilizator HaggisRanca Razvan Haggis Data 7 aprilie 2009 14:33:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000001], b[2000001];

int i,j,m[2000001],sol[2000001];

void kmppre()
{
	i=0;
	j=-1;
	m[i]=j;
	int l2=strlen(a);
	while(i<=l2)
	{
		if(j>=0 && a[i]!=a[j])
			j=m[j];
		++i;
		++j;
		m[i]=j;
	}
}

void kmpmain()
{
	int l1=strlen(b);
	int l2=strlen(a);
	i=0;
	j=0;
	while(i+j<=l1)
		{
			while(b[i+j]==a[j])
				{
					++j;
					if(j==l2)
					{
						++sol[0];
						sol[sol[0]]=i;
					}
				}
			i=i+j-m[j];
			if(j>0)
				j=m[j];
		}
}

int main ()
{
	
	in.get(a, 2000000);
	in.get();
	in.get(b, 2000000);
	kmppre();
	kmpmain();
	out<<sol[0]<<"\n";
	for(i=1;i<=sol[0];i++)
		out<<sol[i]<<" ";
		
	return 0;
}