Pagini recente » Cod sursa (job #1510784) | Cod sursa (job #1362669) | Cod sursa (job #1317469) | Cod sursa (job #3245840) | Cod sursa (job #692476)
Cod sursa(job #692476)
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector <int> sol;
char a[2000001], b[2000001];
const int MOD1 = 100021, MOD2 = 100007, baza = 'z' - '0';
int ha1, hb1, ha2, hb2;
int main(){
freopen ("strmatch.in", "r", stdin), freopen("strmatch.out", "w", stdout);
int i, j, n, m, bn1, bn2;
scanf("%s\n%s", a, b);
n = strlen(a), m = strlen(b);
for (i = 0; i < n; i++)
ha1 = (ha1 * baza + a[i] - '0') % MOD1,
ha2 = (ha2 * baza + a[i] - '0') % MOD2,
hb1 = (hb1 * baza + b[i] - '0') % MOD1,
hb2 = (hb2 * baza + b[i] - '0') % MOD2;
for (i = bn1 = bn2 = 1; i < n; i++)
bn1 = bn1 * baza % MOD1,
bn2 = bn2 * baza % MOD2;
for (i = 0; i < m - n + 1; i++){
if (ha1 == hb1 && ha2 == hb2){
for (j = 0; j < n && a[j] == b[i + j]; j++);
if (j == n) sol.push_back(i);
}
hb1 = (((hb1 - bn1 * (b[i] - '0')) % MOD1 + MOD1) * baza + b[i + n] - '0') % MOD1;
hb2 = (((hb2 - bn2 * (b[i] - '0')) % MOD2 + MOD2) * baza + b[i + n] - '0') % MOD2;
}
printf("%d\n", sol.size());
for (i = 0; i < (int)sol.size(); i++) printf("%d ", sol[i]);
return 0;
}