Pagini recente » Cod sursa (job #293957) | Cod sursa (job #2467712) | Cod sursa (job #953482) | Cod sursa (job #2027726) | Cod sursa (job #2299562)
#include <bits/stdc++.h>
using namespace std;
const int base = 73, mod1 = 100007, mod2 = 100021;
string s, t;
vector<int> ans;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin, s);
getline(fin, t);
int lens = int(s.size()), lent = int(t.size()), high1 = 1, high2 = 1;
int hashs1 = 0, hashs2 = 0, hasht1 = 0, hasht2 = 0;
for(int i = 0; i < lens; ++i){
hashs1 = (base * hashs1 + s[i]) % mod1;
hashs2 = (base * hashs2 + s[i]) % mod2;
hasht1 = (base * hasht1 + t[i]) % mod1;
hasht2 = (base * hasht2 + t[i]) % mod2;
if(i > 0){
high1 = (high1 * base) % mod1;
high2 = (high2 * base) % mod2;
}
}
if(hashs1 == hasht1 && hashs2 == hasht2)
ans.push_back(0);
for(int i = lens; i < lent; ++i){
hasht1 = ((hasht1 - (high1 * t[i - lens]) % mod1 + mod1) * base + t[i]) % mod1;
hasht2 = ((hasht2 - (high2 * t[i - lens]) % mod2 + mod2) * base + t[i]) % mod2;
if(hashs1 == hasht1 && hashs2 == hasht2)
ans.push_back(i - lens + 1);
}
fout << ans.size() << "\n";
for(int i = 0; i < int(ans.size()) && i < 1000; ++i)
fout << ans[i] << " ";
return 0;
}