Pagini recente » Cod sursa (job #2444395) | Cod sursa (job #1268958) | Cod sursa (job #935003) | Cod sursa (job #702273) | Cod sursa (job #1735815)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define DS 62
#define DN 2000005
#define MOD1 666013
#define MOD2 1299709
using namespace std;
int comp_code(char c) {
if (c <= '9')
return c - '0';
if (c <= 'Z')
return c - 'A' + 10;
return c - 'a' + 36;
}
int res[DN];
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, s;
int hp1 = 0, hp2 = 0, hs1 = 0, hs2 = 0, bs1 = 1, bs2 = 1;
int n, m, rs = 0;
fin >> p >> s;
m = p.size();
n = s.size();
if (m > n) {
fout << 0;
return 0;
}
for (int i = 0; i < m; ++i) {
hs1 = (hs1 * DS + comp_code(s[i])) % MOD1;
hs2 = (hs2 * DS + comp_code(s[i])) % MOD2;
hp1 = (hp1 * DS + comp_code(p[i])) % MOD1;
hp2 = (hp2 * DS + comp_code(p[i])) % MOD2;
bs1 = (bs1 * DS) % MOD1;
bs2 = (bs2 * DS) % MOD2;
}
for (int i = m; i < n; ++i) {
if (hs1 == hp1 && hs2 == hp2)
res[rs++] = i - m;
hs1 = (hs1 * DS - (comp_code(s[i-m]) * bs1) % MOD1 + comp_code(s[i]) + MOD1) % MOD1;
hs2 = (hs2 * DS - (comp_code(s[i-m]) * bs2) % MOD2 + comp_code(s[i]) + MOD2) % MOD2;
}
if (hs1 == hp1 && hs2 == hp2)
res[rs++] = n - m;
fout << rs << '\n';
rs = min(rs, 1000);
for (int i = 0; i < rs; ++i)
fout << res[i] << " ";
return 0;
}