Pagini recente » Cod sursa (job #3192360) | Cod sursa (job #2755467) | Cod sursa (job #922309) | Cod sursa (job #266096) | Cod sursa (job #1735810)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define DS 26
#define LL long long
#define MOD1 666013
#define MOD2 1299709
using namespace std;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, s;
vector<int> res;
LL n, m, hp1 = 0, hp2 = 0, hs1 = 0, hs2 = 0, bs1 = 1, bs2 = 1;
fin >> p >> s;
m = p.size();
n = s.size();
if (m > n) {
cout << 0;
return 0;
}
for (int i = 0; i < m; ++i) {
hs1 = (hs1 * DS + s[i] - 'A') % MOD1;
hs2 = (hs2 * DS + s[i] - 'A') % MOD2;
hp1 = (hp1 * DS + p[i] - 'A') % MOD1;
hp2 = (hp2 * DS + p[i] - 'A') % MOD2;
bs1 = (bs1 * DS) % MOD1;
bs2 = (bs2 * DS) % MOD2;
}
for (int i = m; i < n; ++i) {
if (hs1 == hp1 && hs2 == hp2)
res.push_back(i - m);
hs1 = (hs1 * DS - ((s[i-m] - 'A') * bs1) % MOD1 + (s[i] - 'A') % MOD1 + MOD1) % MOD1;
hs2 = (hs2 * DS - ((s[i-m] - 'A') * bs2) % MOD2 + (s[i] - 'A') % MOD2 + MOD2) % MOD2;
}
if (hs1 == hp1 && hs2 == hp2)
res.push_back(n - m);
fout << res.size() << '\n';
int res_size = min((int)res.size(), 1000);
for (int i = 0; i < res_size; ++i)
fout << res[i] << " ";
return 0;
}