Pagini recente » Cod sursa (job #1239380) | Cod sursa (job #1901367) | Cod sursa (job #2797359) | Cod sursa (job #1192616) | Cod sursa (job #2465973)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2 * 1e5 + 5;
const int MOD1 = 666013;
const int MOD2 = 666019;
const int baza = 73;
string a, b;
vector <int> ans;
int hasha1, hasha2;
int hashb1[MAXN], hashb2[MAXN];
int na, nb, p1, p2, cnt, putere1[MAXN], putere2[MAXN];
int main()
{
fin >> a >> b;
na = a.size();
nb = b.size();
if(na > nb) {
fout << "0";
return 0;
}
for(int i = 0; i < na; ++i){
hasha1 = (hasha1 * baza + a[i]) % MOD1;
hasha2 = (hasha2 * baza + a[i]) % MOD2;
(!i) ? putere1[0] = 1 : putere1[i] = putere1[i - 1] * baza % MOD1;
(!i) ? putere2[0] = 1 : putere2[i] = putere2[i - 1] * baza % MOD1;
}
hashb1[0] = b[0], hashb2[0] = b[0];
for(int i = 1; i < nb; ++i){
hashb1[i] = (hashb1[i - 1] * baza + b[i]) % MOD1;
hashb2[i] = (hashb2[i - 1] * baza + b[i]) % MOD2;
}
for(int i = 0; i < nb - na + 1; ++i){
int r = i + na - 1, l = i;
int hb1 = (hashb1[r] - (hashb1[l] * putere1[r - l] ) % MOD1 + MOD1) % MOD1;
int hb2 = (hashb2[r] - (hashb1[l] * putere2[r - l] ) % MOD2 + MOD2) % MOD2;
if(hb1 == hasha1 and hb2 == hasha2)
cnt ++, ans.push_back(r);
}
fout << cnt << '\n';
cnt = 0;
for(auto x : ans){
fout << x << " ", cnt++;
if(cnt > 1000) break;
}
return 0;
}