Cod sursa(job #395653)

Utilizator GotenAmza Catalin Goten Data 13 februarie 2010 16:41:17
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<fstream.h>
#include<iostream.h>
int pre[2000100],c[1100];
char a[2000100],b[2000100];
int main()
{
	int A,B,i,k=0;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(a,2000100);
	f.getline(b,2000100);
	A=strlen(a)-1;
	B=strlen(b)-1;
	for(i=2;i<=A;i++)
	{
		while(k&&a[k+1]!=a[i])
			k=pre[k];
		if(a[k+1]==a[i])
			k++;
		pre[i]=k;
	}
	k=0;
	for(i=1;i<=B;i++)
	{
		while(k&&a[k+1]!=b[i])
			k=pre[k];
		if(a[k+1]==b[i])
			k++;
		if(k==A)
		{
			c[++c[0]]=i-A;
			if(c[0]==1000)
				i=B+1;
		}
	}
	g<<c[0]<<'\n';
	for(i=1;i<=c[0];i++)
		g<<c[i]<<' ';
	return 0;
}