Pagini recente » Cod sursa (job #1400789) | Cod sursa (job #1421159) | Cod sursa (job #110373) | Borderou de evaluare (job #2387029) | Cod sursa (job #692160)
Cod sursa(job #692160)
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector <int> sol;
char a[2000001], b[2000001];
const int MOD = 999983, baza = 'z' - '0';
int p;
int main(){
freopen ("strmatch.in", "r", stdin), freopen("strmatch.out", "w", stdout);
int i, j, n, m, ha, hb, bn;
scanf("%s\n%s", a, b);
n = strlen(a), m = strlen(b);
for (i = ha = 0; i < n; i++)
ha = (ha * baza + a[i] - '0') % MOD;
for (i = hb = 0; i < n; i++)
hb = (hb * baza + b[i] - '0') % MOD;
for (i = bn = 1; i < n; i++) bn = (bn * baza) % MOD;
for (i = 0; i < m - n; i++){
if (ha == hb){
for (j = 0; j < n && a[j] == b[i + j]; j++);
if (j == n) sol.push_back(i);
}
hb = ((hb - bn * (b[i] - '0')) * baza + b[i + n] - '0') % MOD;
}
printf("%d\n", sol.size());
for (i = 0; i < (int)sol.size() && i < 1000; i++)
printf("%d ", sol[i]);
return 0;
}