Cod sursa(job #932586)

Utilizator radu193Constantinescu Radu radu193 Data 29 martie 2013 00:57:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<algorithm>
#include<cstdio>
#include<fstream>
#include<cstring>
#define NM 2000005
using namespace std;
char a[NM], b[NM];
int pr[NM];
int main()
{
	
	int i, j, n, m, r, nr = 0,poz[1005];
	
	ifstream f ("strmatch.in");
	f>>a>>b;
	n = strlen(a), m = strlen(b);
	
	j = 0;
	pr[1] = 0;

	for(i = 2; i <= n; i++)
	{
		while ( j>0 && a[j] != a[i-1])
			j = pr[j];
		if(a[j]==a[i-1])
			j++;
		pr[i] = j;
	}
	freopen("strmatch.out", "w", stdout);
	r = 0;
	for(i = 1; i<=m; i++)
	{
		while( r>0 && b[i-1] != a[r])
				r = pr[r];
		if(b[i-1] == a[r])
			r++;
		if(r == n)
		{
			r = pr[r],nr++;
			if(nr <=1000) poz[nr] = i - n;
		}
				
	}
	printf("%i\n", nr);
	for(i = 1; i<= min(nr, 1000); i++)
		printf("%i ", poz[i]);
	return 0;
}