Cod sursa(job #685665)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 21 februarie 2012 08:44:11
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
#include<string.h>
#define lim 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[lim],M[lim];
long long k,i,p[lim],z,Sol[lim],q,n,m;
int main (){
	f>>(N+1);
	f>>(M+1);
	n=strlen(N+1);
	m=strlen(M+1);
	k=0;
	p[1]=0;
	for(i=2;i<=n;i++){
		while(k>0  && N[k+1]!=N[i])
			k=p[k];
		if(N[k+1]==N[i])
			k++;
		p[i]=k;
	}
	q=0;
	for(i=1;i<=m;i++){
		while(q>0 && N[q+1]!=M[i])
			q=p[q];
		if(N[q+1]==M[i])
			q++;
		if(q==n){
			z++;
			Sol[z]=i-q;
		}
	}
	g<<z<<"\n";
	if(z>1000)
		z=1000;
	for(i=1;i<=z;i++)
		g<<Sol[i]<<" ";
	g<<"\n";
	return 0;
}