Cod sursa(job #932526)

Utilizator radu193Constantinescu Radu radu193 Data 28 martie 2013 23:45:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<string.h>
#define NM 2000000
int main()
{
	char a[NM], b[NM];
	int pr[NM], i, j, n, m, r, nr = 0,poz[NM];
	freopen("strmatch.in", "r", stdin);
	scanf("%s%s",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;
		//printf("%c %c\n", a[i-1], a[j]);
		//printf("%i\n", pr[i]);
		
	}
	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)
			nr++, poz[nr] = i - n+1;
	}
	printf("%i\n", nr);
	for(i = 1; i<=nr;i++)
		printf("%i ", poz[i]);
	return 0;
}