Pagini recente » Cod sursa (job #956302) | Cod sursa (job #1828714) | Cod sursa (job #555055) | Cod sursa (job #2517991) | Cod sursa (job #3153674)
#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 = 10027, baza = 73;
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.push_back(i - a.size() + 1);
}
cout << rez.size() << '\n';
for(int i = 0; i < min(1000, (int) rez.size()); ++i) cout << rez[i] << ' ';
return 0;
}