Pagini recente » Cod sursa (job #2943890) | Cod sursa (job #1803847) | Cod sursa (job #1034927) | Cod sursa (job #2327549) | Cod sursa (job #2955529)
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000009
#define baza 997
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
ll hasha, hashb, p = 1, dim, rez[1005];
int main() {
fin >> a >> b;
if (b.size() < a.size()) {
fout << 0;
return 0;
}
int l = a.size();
for (int i = 0; i < l; ++i) {
hasha = (hasha * baza + a[i]) % MOD;
if (i != 0)
p = (p * baza) % MOD;
}
for (int i = 0; i < l; ++i)
hashb = (hashb * baza + b[i]) % MOD;
if (hasha == hashb)
++dim;
for (int i = l; i < b.size(); ++i) {
hashb = ((hashb - (1LL * b[i - l] * p) % MOD + MOD) * baza + b[i]) % MOD;
if (hasha == hashb)
{
++dim;
if(dim <= 1000)
rez[dim] = i - l + 1;
}
}
fout << dim << "\n";
for (int i = 1; i <= min(1000LL, dim); ++i)
fout << rez[i] << " ";
return 0;
}