Pagini recente » Cod sursa (job #643652) | Cod sursa (job #1647946) | Cod sursa (job #2827949) | Cod sursa (job #1317192) | Cod sursa (job #3153650)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
long long hash1, hash2, p1, p2, aux1 = 1, aux2 = 1;
int MOD1 = 666013, MOD2 = 1e9 + 7, baza = 57;
vector<int> rez;
int main()
{
cin >> a >> b;
for(int i = 0; i < a.size(); ++i) {
hash1 = (hash1 * baza + a[i]) % MOD1;
hash2 = (hash2 * baza + a[i]) % MOD2;
if(i) aux1 = (aux1 * baza) % MOD1, aux2 = (aux2 * baza) % MOD2;
}
for(int i = 0; i < a.size(); ++i) {
p1 = (p1 * baza + b[i]) % MOD1;
p2 = (p2 * baza + b[i]) % MOD2;
}
if(p1 == hash1 && p2 == hash2) rez.push_back(0);
for(int i = a.size(); i < b.size(); ++i) {
p1 = ((((p1 - aux1 * b[i - a.size()]) % MOD1) + MOD1) * baza + b[i]) % MOD1;
p2 = ((((p2 - aux2 * b[i - a.size()]) % MOD2) + MOD2) * baza + b[i]) % MOD2;
if(p1 == hash1 && p2 == hash2 && rez.size() <= 1000) rez.push_back(i - a.size() + 1);
}
cout << rez.size() << '\n';
for(int i = 0; i < rez.size(); ++i) cout << rez[i] << ' ';
return 0;
}