Pagini recente » Monitorul de evaluare | Borderou de evaluare (job #2626275) | Cod sursa (job #652248) | Cod sursa (job #539735) | Cod sursa (job #3340906)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int base = 127;
const int mod1 = 666013;
const int mod2 = 1e9 + 7;
vector <int> sol;
void rabinkarp (string a, string b)
{
int n = a.size ();
int m = b.size ();
if (n > m)
{
fout << 0;
return;
}
int hashA1 = 0, hashA2 = 0;
int power1 = 1, power2 = 1;
for (int i = 0; i < n; i++)
{
hashA1 = (hashA1 * base + a[i]) % mod1;
hashA2 = (hashA2 * base + a[i]) % mod2;
if (i != n - 1)
{
power1 = power1 * base % mod1;
power2 = power2 * base % mod2;
}
}
int hashB1 = 0, hashB2 = 0;
for (int i = 0; i < n; i++)
{
hashB1 = (hashB1 * base + b[i]) % mod1;
hashB2 = (hashB2 * base + b[i]) % mod2;
}
if (hashB1 == hashA1 && hashB2 == hashA2)
sol.push_back (0);
for (int i = n; i < m; i++)
{
hashB1 = ((hashB1 - b[i - n] * power1 % mod1 + mod1) * base + b[i]) % mod1;
hashB2 = ((hashB2 - b[i - n] * power2 % mod2 + mod2) * base + b[i]) % mod2;
if (hashB1 == hashA1 && hashB2 == hashA2)
sol.push_back (i - n + 1);
}
}
signed main ()
{
string a, b;
fin >> a >> b;
rabinkarp (a, b);
fout << sol.size () << '\n';
int limit = min ((int)sol.size (), 1000LL);
for (int i = 0; i < limit; i++)
fout << sol[i] << " ";
return 0;
}