Pagini recente » Cod sursa (job #1809889) | Cod sursa (job #1546729) | Cod sursa (job #1160483) | Cod sursa (job #2498261) | Cod sursa (job #2920433)
#include <bits/stdc++.h>
#define NHASH1 100007
#define NHASH2 100021
#define BASE 128
#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]) % NHASH1;
patternhash2 = (patternhash2 * BASE + pattern[i]) % NHASH2;
if (i < np - 1) {
crthash1 = (crthash1 * BASE + s[i]) % NHASH1;
crthash2 = (crthash2 * BASE + s[i]) % NHASH2;
}
if (i > 0) {
power1 = (power1 * BASE) % NHASH1;
power2 = (power2 * BASE) % NHASH2;
}
}
nsol = 0;
for (i = np - 1; i < ns; i++) {
crthash1 = (crthash1 * BASE + s[i]) % NHASH1;
crthash2 = (crthash2 * BASE + s[i]) % NHASH2;
if (crthash1 == patternhash1 && crthash2 == patternhash2)
vsol[nsol++] = i - np + 1;
crthash1 = (crthash1 - (power1 * s[i - np + 1]) % NHASH1 + NHASH1) % NHASH1;
crthash2 = (crthash2 - (power2 * s[i - np + 1]) % NHASH2 + NHASH2) % NHASH2;
}
fout << nsol << "\n";
for (i = 0; i < nsol && i < 1000; i++)
fout << vsol[i] << " ";
return 0;
}