Pagini recente » Cod sursa (job #2347684) | Cod sursa (job #3178782) | Cod sursa (job #2454257) | Cod sursa (job #2619855) | Cod sursa (job #2789479)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MOD1 100007
#define MOD2 100021
#define P 73
int n, m, h, hp, p1, p2, h1, h2;
char v[2000005];
char a[2000005], b[2000005];
int main() {
fin >> a >> b;
n = strlen(a);
m = strlen(b);
p1 = p2 = 1;
for (int i=0;i<n;i++){
h = (h * P + a[i]) % MOD1;
hp = (hp * P + a[i]) % MOD2;
if (i != 0){
p1 = (p1 * P) % MOD1;
p2 = (p2 * P) % MOD2;
}
}
if (n > m){
fout << "0\n";
return 0;
}
for (int i=0;i<n;i++){
h1 = (h1 * P + b[i]) % MOD1;
h2 = (h2 * P + b[i]) % MOD2;
}
int ans = 0;
if (h1 == h && h2 == hp){
v[0] = 1;
ans ++;
}
for (int i=n;i<m;i++){
h1 = ((h1 - (b[i-n] * p1) % MOD1 + MOD1) * P + b[i]) % MOD1;
h2 = ((h2 - (b[i-n] * p2) % MOD2 + MOD2) * P + b[i]) % MOD2;
if (h1 == h && h2 == hp)
v[i - n + 1] = 1, ans ++;
}
fout << ans << '\n';
ans = 0;
for (int i=0;i<m && ans < 1000;i++)
if (v[i])
ans ++, fout << i << ' ';
fout << '\n';
return 0;
}