Pagini recente » Cod sursa (job #1545487) | Cod sursa (job #806324) | Cod sursa (job #1412820) | Cod sursa (job #1021846) | Cod sursa (job #984370)
Cod sursa(job #984370)
#include <cstdio>
#include <iostream>
#include <cstring>
const int pb = 257;
const int MOD = 1000000007;
long long power(long long x, unsigned a)
{
if(a == 0) return 1;
if(a == 1) return x % MOD;
if(a % 2 == 0) return (power((x * x) % MOD, a / 2)) % MOD;
return (x * power((x * x) % MOD, a / 2)) % MOD;
}
long long getHash(char *str, int a)
{
long long ret = 0;
for(int i = 0; i < a; i++)
ret = (ret * pb + str[i]) % MOD;
return ret;
}
bool compare(char *str, char *strl, int delay, int start)
{
for(unsigned i = 0; i < start; i++)
if(str[i] != strl[delay + i]) return false;
return true;
}
unsigned rabin(char *str, char *strl, int *nArr)
{
unsigned nr = 0, a = strlen(str), b = strlen(strl);
long long comp = getHash(str, strlen(str)), to = getHash(strl, strlen(str)), pow = power(pb, strlen(str));
if(comp == to)
{
if(compare(str, strl, 0, a))
{
nArr[nr] = 0;
nr++;
}
}
for(int i = a; i < b; i++)
{
to = to * pb + strl[i];
to %= MOD;
to -= (pow * strl[i - a]) % MOD;
if(to < 0) to += MOD;
if(comp == to)
{
if(compare(str, strl, i - a + 1, a))
{
if(nr < 1000) nArr[nr] = i - a + 1;
nr++;
}
}
}
return nr;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char *str = new char[2000000], *strl = new char[2000000];
int *nArr = new int[1000];
gets(str);
gets(strl);
int nr = rabin(str, strl, nArr), a;
printf("%d \n", nr);
if(nr < 1000) a = nr;
else a = 1000;
for(int i = 0; i < a; i++)
printf("%d ", nArr[i]);
return 0;
}