Pagini recente » Cod sursa (job #1294521) | Cod sursa (job #1989108) | Cod sursa (job #1913695) | Cod sursa (job #532522) | Cod sursa (job #2678344)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 2000001
#define MOD1 100007
#define MOD2 100021
#define D 73
using namespace std;
char pattern[MAXN], text[MAXN];
bool match[MAXN];
int m,n,nr,hashp1,hashp2,d1,d2;
int hasht1,hasht2;
void Rabin_Karp()
{
n=strlen(pattern);
m=strlen(text);
d1=d2=1, hashp1=hashp2=0;
for(int i=0; i<n; ++i)
{
hashp1 = (hashp1 * D + pattern[i]) % MOD1;
hashp2 = (hashp2 * D + pattern[i]) % MOD2;
if(i)
{
d1=(d1*D)%MOD1;
d2=(d2*D)%MOD1;
}
}
for (int i=0; i<n; ++i)
hasht1 = (hasht1 * D + text[i]) % MOD1,
hasht2 = (hasht2 * D + text[i]) % MOD2;
if (hasht1 == hashp1 && hasht2 == hashp2)
match[0]=true, nr++;
for (int i=n;i<m;++i)
{
hasht1 = ((hasht1 - (text[i-n] * d1) % MOD1 + MOD1) * D + text[i]) % MOD1;
hasht2 = ((hasht2 - (text[i-n] * d2) % MOD2 + MOD2) * D + text[i]) % MOD2;
if (hasht1 == hashp1 && hasht2 == hashp2)
match[i-n+1]=true, nr++;
}
printf("%d\n", nr);
nr=0;
for (int i=0;nr<1000 && i<m;++i)
if (match[i])
{
printf("%d ", i);
nr++;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", pattern, text);
if (n > m)
{
printf("0");
return 0;
}
Rabin_Karp();
return 0;
}