Pagini recente » Cod sursa (job #1153998) | Cod sursa (job #396737) | Cod sursa (job #2673114) | Cod sursa (job #1634941) | Cod sursa (job #2919071)
#include <bits/stdc++.h>
#define NHASH1 666013
#define NHASH2 666023
#define BASE 26
#define NSOLMAX 1000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int vsol[NSOLMAX + 1];
int main() {
int np, ns, patternhash1, patternhash2, crthash1, crthash2, power1, power2, nsol, i;
string pattern, s;
fin >> pattern >> s;
np = pattern.size();
ns = s.size();
patternhash1 = patternhash2 = crthash1 = crthash2 = 0;
power1 = power2 = 1;
for (i = 0; i < np; i++) {
patternhash1 = (patternhash1 * BASE + pattern[i] - 'A') % NHASH1;
patternhash2 = (patternhash2 * BASE + pattern[i] - 'A') % NHASH2;
if (i < np - 1) {
crthash1 = (crthash1 * BASE + s[i] - 'A') % NHASH1;
crthash2 = (crthash2 * BASE + s[i] - 'A') % NHASH2;
}
if (i > 0) {
power1 = (power1 * BASE) % NHASH1;
power2 = (power2 * BASE) % NHASH2;
}
}
nsol = 0;
for (i = np - 1; i < ns && nsol < NSOLMAX; i++) {
crthash1 = (crthash1 * BASE + s[i] - 'A') % NHASH1;
crthash2 = (crthash2 * BASE + s[i] - 'A') % NHASH2;
if (crthash1 = patternhash1 && crthash2 == patternhash2)
vsol[nsol++] = i - np + 1;
crthash1 = (crthash1 - power1 * (s[i - np + 1] - 'A') + NHASH1) % NHASH1;
crthash2 = (crthash2 - power2 * (s[i - np + 1] - 'A') + NHASH2) % NHASH2;
}
fout << nsol << "\n";
for (i = 0; i < nsol; i++)
fout << vsol[i] << " ";
return 0;
}