Pagini recente » Cod sursa (job #614165) | Cod sursa (job #1164962) | Cod sursa (job #3138674) | Cod sursa (job #2757660) | Cod sursa (job #147382)
Cod sursa(job #147382)
#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, 100007);
printf("%d\n", SOL);
for (int i=1; i<=SOL; i++)
printf("%d ", sol[i]);
return 0;
}