Pagini recente » Cod sursa (job #3166000) | Cod sursa (job #1547471) | Cod sursa (job #2386395) | Cod sursa (job #3128606)
#include <iostream>
#include <stdio.h>
#define NMAX 2000001
#define HASHBASE1 256
#define HASHSIZE1 4999999
#define HASHBASE2 256
#define HASHSIZE2 666013
char str[NMAX];
int nstr;
char pat[NMAX];
int npat;
int ap[NMAX];
int phash1, phash2, shash1, shash2;
using namespace std;
int lgput(int a, int n, int mod) {
int p;
p = 1;
while (n>0) {
if (n%2==1) {
p = (long long)p * a % mod;
}
a = (long long)a * a % mod;
n/=2;
}
return p;
}
int main() {
FILE *fin, *fout;
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
int i, nrap, pow1, pow2;
char ch;
npat = 0;
ch = fgetc(fin);
while (ch>='A' && ch<='Z') {
pat[npat] = ch;
npat++;
ch = fgetc(fin);
}
nstr = 0;
while (ch<'A' || ch>'Z') {
ch = fgetc(fin);
}
while (ch>='A' && ch<='Z') {
str[nstr] = ch;
nstr++;
ch = fgetc(fin);
}
pow1 = lgput(HASHBASE1, npat-1, HASHSIZE1);
pow2 = lgput(HASHBASE2, npat-1, HASHSIZE2);
for (i=0; i<npat; i++) {
phash1 = (phash1*HASHBASE1 + pat[i])%HASHSIZE1;
phash2 = (phash2*HASHBASE2 + pat[i])%HASHSIZE2;
shash1 = (shash1*HASHBASE1 + str[i])%HASHSIZE1;
shash2 = (shash2*HASHBASE2 + str[i])%HASHSIZE2;
}
nrap = 0;
for (i=npat; i<nstr; i++) {
if (phash1==shash1 && phash2==shash2) {
ap[nrap] = i-npat;
nrap++;
}
///remove
shash1 = (shash1-str[i-npat]*pow1)%HASHSIZE1;
if (shash1<0) {
shash1+=HASHSIZE1;
}
shash2 = (shash2-str[i-npat]*pow2)%HASHSIZE2;
if (shash2<0) {
shash2+=HASHSIZE2;
}
///add
shash1 = (shash1*HASHBASE1 + str[i])%HASHSIZE1;
shash2 = (shash2*HASHBASE2 + str[i])%HASHSIZE2;
}
fprintf(fout, "%d\n", nrap);
for (i=0; i<nrap; i++) {
fprintf(fout, "%d ", ap[i]);
}
fclose(fin);
fclose(fout);
return 0;
}