Cod sursa(job #147376)

Utilizator the1dragonIonita Alexandru the1dragon Data 2 martie 2008 20:52:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
#include<string.h>
int n, m, SOL, sol[1024];
char sir[2000002], model[2000002];
	

void rabinkarp(char * T, char * P, int d, int q)
{
	int i, h=1, p, t, s, f;
	for (i=1; i<m; i++)
		h=(h*d)%q;
	p=0;
	t=0;
	for (i=1; i<=m; i++)
	{
		p=(d*p+P[i])%q;
		t=(d*t+T[i])%q;
	}
	for (s=0; s<=n-m; s++)
	{
		if (p==t)
		{
			f=0;
			
			for (i=1; i<=m; i++)
				if (P[i]!=T[s+i]) 
				{
					f=1;
					break;
				}
			if (!f) 
			{
				//printf("Modelul apare cu deplasamentul %d\n", s);
				++SOL;
				if (SOL<=1000)
					sol[SOL]=s;
			}
		}				
		if (s<n-m)
			t=(d*(q+t-(T[s+1]*h)%q)+T[s+m+1])%q;
	}
}

int main()
{
	//freopen("rabin-karp.in", "r", stdin);
	freopen("strmatch.in", "r", stdin);
	//freopen("rabin-karp.out", "w", stdout);
	freopen("strmatch.out", "w", stdout);
	
	gets(model+1);
	gets(sir+1);
	
	n=strlen(sir+1);
	m=strlen(model+1);
	//scanf("%d", &n);
	//int i;
	//for (i=1; i<=n; i++)
	//	scanf("%c", &sir[i]);
	//scanf("%d", &m);
	//for (i=1; i<=m; i++)
	//	scanf("%c", &model[i]);
	rabinkarp(sir, model, 256, 239137);
	printf("%d\n", SOL);
	for (int i=1; i<=SOL; i++)
		printf("%d ", sol[i]);
	return 0;
}