Pagini recente » Cod sursa (job #1393541) | Cod sursa (job #2566287) | Cod sursa (job #910333) | Cod sursa (job #927663) | Cod sursa (job #2812986)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int p = 31;
const int mod = 1e9 + 9;
const int maxN = 2e6 + 5;
long long pow[maxN];
long long h[maxN];
vector <int> ans;
int main() {
string s; fin >> s;
string t; fin >> t;
if(s.size() > t.size()) { fout << '0'; return 0;}
long long Hash = 0, pow = 1;
for(int i = 0; i < s.size(); ++i) {
Hash = (Hash * p + (s[i] - 'A'+1)) % mod;
if(i != 0) pow = pow * p % mod;
}
long long subH = 0;
for(int i = 0; i < t.size(); ++i) {
if(i + 1 <= s.size()) {
subH = (subH * p + (t[i]-'A'+1)) % mod;
} else {
subH = (subH - (pow * (t[i-s.size()]-'A'+1)) % mod + mod) % mod;
subH = (subH * p + (t[i]-'A'+1)) % mod;
if(subH == Hash) {
if(ans.size() < 1000)
ans.push_back(i);
else i = t.size();
}
}
}
fout << ans.size() << '\n';
for(int i : ans)
fout << i - s.size() + 1 << " ";
return 0;
}