Cod sursa(job #932539)

Utilizator radu193Constantinescu Radu radu193 Data 28 martie 2013 23:54:58
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
#include<string.h>
#define NM 2000005
int main()
{
	char a[NM], b[NM];
	int pr[NM], i, j, n, m, r, nr = 0,poz[1005];
	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)
		{
			r = pr[r],nr++;
			if(nr <=1000) poz[nr] = i - n;
		}
				
	}
	printf("%i\n", nr);
	for(i = 1; i<=nr;i++)
		printf("%i ", poz[i]);
	return 0;
}