Cod sursa(job #489262)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 2 octombrie 2010 09:51:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
// infoarena: problema/strmatch //
#include <fstream>
#include <cstring>
#define MAXN 2000100
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

char a[MAXN],b[MAXN];
int i,j,n,m,l[MAXN],k,q,r[MAXN];

int main()
{
	in>>a>>b;
	
	n = strlen(a);
	m = strlen(b);
	
	l[0] = 0;
	for(i=1; i<n; i++)
	{
		while(k>0 && a[k] != a[i])
			k = l[k];
		if(a[k] == a[i])
			k++;
		l[i] = k;
	}
	
	k=0;
	for(i=0; i<m; i++)
	{
		while(k>0 && a[k] != b[i])
			k=l[k-1];
		if(a[k] == b[i])
			k ++;
		if(k == n)
		{
			r[++q] = i-n+1;
			k = l[k-1];
		}
	}
	out<<q<<'\n';
	for(i=1; i<=q; i++)
		out<<r[i]<<' ';
	
	return 0;
}