Pagini recente » Cod sursa (job #2658670) | Cod sursa (job #665699) | Cod sursa (job #329834) | Cod sursa (job #2613950) | Cod sursa (job #2979042)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int mod1 = 100007;
const int mod2 = 100021;
const int kN = 2e6 + 5;
int cnt;
long long h1[kN], h2[kN], hS1, hS2;
char s[kN], t[kN];
bitset<kN>used;
int main(){
ios_base::sync_with_stdio(false);
fin >> s >> t;
int S = (int)strlen(s);
int T = (int)strlen(t);
if (S > T){
fout << 0;
return 0;
}
long long p1 = 1, p2 = 1;
for (int i = 0; i < S; i++){
hS1 = (hS1 + (s[i] - 'A' + 1) * p1) % mod1;
hS2 = (hS2 + (s[i] - 'A' + 1) * p2) % mod2;
p1 = (p1 * 76) % mod1;
p2 = (p2 * 76) % mod2;
}
p1 = p2 = 1;
for (int i = 0; i < T; i++){
h1[i + 1] = (h1[i] + (t[i] - 'A' + 1) * p1) % mod1;
h2[i + 1] = (h2[i] + (t[i] - 'A' + 1) * p2) % mod2;
p1 = (p1 * 76) % mod1;
p2 = (p2 * 76) % mod2;
}
p1 = p2 = 1;
for (int i = 0; i + S - 1 < T; i++){
long long cur_h1 = (h1[i + S] - h1[i] + mod1) % mod1;
long long cur_h2 = (h2[i + S] - h2[i] + mod2) % mod2;
if (cur_h1 == (hS1 * p1) % mod1 && cur_h2 == (hS2 * p2) % mod2){
used[i] = true;
++cnt;
}
p1 = (p1 * 76) % mod1;
p2 = (p2 * 76) % mod2;
}
fout << cnt << '\n';
cnt = 0;
for (int i = 0; i < T; i++){
if (used[i] && cnt < 1000){
fout << i << " ";
++cnt;
}
}
}