Pagini recente » Cod sursa (job #2205450) | Cod sursa (job #490155) | Cod sursa (job #2478772) | Cod sursa (job #2274439) | Cod sursa (job #2167185)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1 = 100007, mod2 = 100021, MaxN = 1e6 * 2 + 5, Base = 179;
char a[MaxN], b[MaxN];
int main()
{
f >> a >> b;
int na = strlen(a), nb = strlen(b);
if (nb < na) {
g << 0 << '\n';
return 0;
}
int hashA1 = 0, hashA2 = 0, hashB1 = 0, hashB2 = 0, kB1 = 1, kB2 = 1;
for (int i = 0; i < na; ++i) {
hashA1 = (Base * hashA1 + a[i]) % mod1;
hashA2 = (Base * hashA2 + a[i]) % mod2;
hashB1 = (Base * hashB1 + b[i]) % mod1;
hashB2 = (Base * hashB2 + b[i]) % mod2;
}
for (int i = 1; i < na; ++i) {
kB1 = (kB1 * Base) % mod1;
kB2 = (kB2 * Base) % mod2;
}
vector<int> ans;
int rez = 0;
if (hashA1 == hashB1 && hashA2 == hashB2) ++rez, ans.push_back(0);
for (int i = na; i < nb; ++i) {
hashB1 = (hashB1 - kB1 * b[i - na]) % mod1 + mod1;
hashB2 = (hashB2 - kB2 * b[i - na]) % mod2 + mod2;
hashB1 = (Base * hashB1 + b[i]) % mod1;
hashB2 = (Base * hashB2 + b[i]) % mod2;
if (hashA1 == hashB1 && hashA2 == hashB2) {
++rez;
if (rez <= 1000) ans.push_back(i - na + 1);
}
}
g << rez << '\n';
for (auto x: ans) g << x << ' ';
return 0;
}