Pagini recente » Cod sursa (job #626650) | Cod sursa (job #1309306) | Cod sursa (job #2725007) | Cod sursa (job #2430401) | Cod sursa (job #2978788)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int kN = 2e6 + 5;
const int mod = 1e9 + 9;
long long h[kN];
char s[kN], t[kN];
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 p = 1;
for (int i = 0; i < T; i++){
h[i + 1] = (h[i] + (t[i] - 'A' + 1) * p) % mod;
p = (p * 31) % mod;
}
p = 1;
long long hash_s = 0;
for (int i = 0; i < S; i++){
hash_s = (hash_s + (s[i] - 'A' + 1) * p) % mod;
p = (p * 31) % mod;
}
vector<int>ans;
p = 1;
for (int i = 0; i + S - 1 < T; i++){
long long cur_h = (h[i + S] - h[i] + mod) % mod;
if (cur_h == (hash_s * p) % mod){
ans.push_back(i);
}
p = (p * 31) % mod;
}
fout << (int)ans.size() << '\n';
for (int i = 0; i < min(1000, (int)ans.size()); i++){
fout << ans[i] << ' ';
}
}