Pagini recente » Cod sursa (job #708943) | Cod sursa (job #1251444) | Cod sursa (job #3173564) | Cod sursa (job #1497845) | Cod sursa (job #2916964)
#include <iostream>
#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int p = 37;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
vector <int> ans;
signed main()
{
string t; fin >> t;
string s; fin >> s;
int P1 = 1, P2 = 1;
for(int i = 1; i < t.size(); ++i) {
P1 = P1 * p % mod1;
P2 = P2 * p % mod2;
}
int H1 = 0, H2 = 0;
for(int i = 0; i < t.size(); ++i) {
H1 = (H1 * p % mod1 + (t[i] + 1)) % mod1;
H2 = (H2 * p % mod2 + (t[i] + 1)) % mod2;
}
int hash1 = 0, hash2 = 0;
for(int i = 0; i < s.size(); ++i)
{
if(i >= t.size()) {
hash1 = (hash1 - P1 * (s[i-t.size()] + 1) % mod1 + mod1) % mod1;
hash2 = (hash2 - P2 * (s[i-t.size()] + 1) % mod2 + mod2) % mod2;
}
hash1 = (hash1 * p % mod1 + (s[i] + 1)) % mod1;
hash2 = (hash2 * p % mod2 + (s[i] + 1)) % mod2;
if(H1 == hash1 && H2 == hash2)
ans.push_back(i - t.size() + 1);
//cout << hash1 << " " << hash2 << " --> " << H1 << " " << H2 << '\n';
}
fout << ans.size() << "\n";
for(int i = 0; i < min((int)ans.size(), (int)1000); ++i)
fout << ans[i] << " ";
return 0;
}