Pagini recente » Cod sursa (job #728830) | Cod sursa (job #2478086) | Cod sursa (job #1994227) | Cod sursa (job #2955676) | Cod sursa (job #2452028)
//Rabin-Karp
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define fs first
#define sc second
#define pii pair <int, int>
#define Nmax 2000005
#define MOD1 666013
#define MOD2 100007
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[Nmax], b[Nmax];
int ha1, ha2;
int hb1, hb2;
queue <int> Q;
int ans, p1=1, p2=1;
int main()
{
f >> a >> b;
int la=strlen(a), lb=strlen(b);
if (la > lb)
{
g << "0";
return 0;
}
for (int i = 0; i < la; i++)
{
ha1 = ha1 * 73 + a[i]; ha1 %= MOD1;
ha2 = ha2 * 73 + a[i]; ha2 %= MOD2;
hb1 = hb1 * 73 + b[i]; hb1 %= MOD1;
hb2 = hb2 * 73 + b[i]; hb2 %= MOD2;
if (i != 0)
{
p1 = p1 * 73; p1 %= MOD1;
p2 = p2 * 73; p2 %= MOD2;
}
}
if (ha1 == hb1 && ha2 == hb2)
{
ans++;
Q.push(0);
}
for (int i = la; i < lb; i++)
{
hb1 = ((hb1 - (p1*b[i-la])%MOD1 + MOD1) % MOD1) * 73 + b[i]; hb1%=MOD1;
hb2 = ((hb2 - (p2*b[i-la])%MOD2 + MOD2) % MOD2) * 73 + b[i]; hb2%=MOD2;
if (hb1 == ha1 && ha2 == hb2)
{
ans++;
if (Q.size() < 1000) Q.push(i-la+1);
}
}
g << ans << '\n';
while (!Q.empty())
{
g << Q.front() << " ";
Q.pop();
}
return 0;
}