Pagini recente » Cod sursa (job #933295) | Cod sursa (job #510618) | Cod sursa (job #2874870) | Cod sursa (job #1987212) | Cod sursa (job #2919074)
#include <bits/stdc++.h>
#define NHASH1 131072
#define NHASH2 262144
#define BASE 63
#define NSOLMAX 1000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int vsol[NSOLMAX + 1];
map <char, int> mpval;
void prec_map() {
int i;
char ch;
i = 0;
for (ch = 'a'; ch <= 'z'; ch++)
mpval[ch] = i++;
for (ch = 'A'; ch <= 'Z'; ch++)
mpval[ch] = i++;
for (ch = '0'; ch <= '9'; ch++)
mpval[ch] = i++;
}
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();
prec_map();
patternhash1 = patternhash2 = crthash1 = crthash2 = 0;
power1 = power2 = 1;
for (i = 0; i < np; i++) {
patternhash1 = (patternhash1 * BASE + mpval[pattern[i]]) % NHASH1;
patternhash2 = (patternhash2 * BASE + mpval[pattern[i]]) % NHASH2;
if (i < np - 1) {
crthash1 = (crthash1 * BASE + mpval[s[i]]) % NHASH1;
crthash2 = (crthash2 * BASE + mpval[s[i]]) % 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 + mpval[s[i]]) % NHASH1;
crthash2 = (crthash2 * BASE + mpval[s[i]]) % NHASH2;
if (crthash1 = patternhash1 && crthash2 == patternhash2)
vsol[nsol++] = i - np + 1;
crthash1 = (crthash1 - (power1 * mpval[s[i - np + 1]]) % NHASH1 + NHASH1) % NHASH1;
crthash2 = (crthash2 - (power2 * mpval[s[i - np + 1]]) % NHASH2 + NHASH2) % NHASH2;
}
fout << nsol << "\n";
for (i = 0; i < nsol; i++)
fout << vsol[i] << " ";
return 0;
}