Pagini recente » Cod sursa (job #742409) | Cod sursa (job #3309367) | Cod sursa (job #13743) | Cod sursa (job #3344746) | Cod sursa (job #3355846)
#include <stdio.h>
#define D 1
#define MAXLEN 2000000
#define BASE 73
#define MODULO1 1000000019
#define MODULO2 1000000021
#define SIGMA 26
char trans[128];
char a[MAXLEN+1], b[MAXLEN+1];
int pos[MAXLEN];
int n, m;
unsigned long long ahash1, ahash2, powerBase1, powerBase2;
void preGen(){
int i;
for(i = 0; i < SIGMA; i++)
trans[i+'a'] = i;
for(i = 0; i < SIGMA; i++)
trans[i + 'A'] = i + SIGMA;
for(i = 0; i < 10; i++)
trans[i + '0'] = i + 2*SIGMA;
}
void readSir(){
FILE *in;
int i;
in = fopen("strmatch.in", "r");
n = 0;
do{
a[n++] = fgetc(in);
}while(a[n-1] != '\n');
n--;
m = 0;
do{
b[m++] = fgetc(in);
}while(b[m-1] != '\n' && b[m-1] != EOF);
m--;
fclose(in);
ahash1 = ahash2 = 0;
powerBase1 = powerBase2 = 1;
i = 0;
ahash1 = (ahash1*BASE + trans[(int)a[i]])%MODULO1;
ahash2 = (ahash2*BASE + trans[(int)a[i]])%MODULO2;
for(i = 1; i < n; i++){
powerBase1 = (powerBase1*BASE)%MODULO1;
powerBase2 = (powerBase2*BASE)%MODULO2;
ahash1 = (ahash1*BASE + trans[(int)a[i]])%MODULO1;
ahash2 = (ahash2*BASE + trans[(int)a[i]])%MODULO2;
}
}
void displayAp(){
FILE *out;
unsigned long long windowHash1, windowHash2;
int i, times;
windowHash1 = windowHash2 = 0;
for(i = 0; i < n; i++){
windowHash1 = (windowHash1 * BASE + trans[(int)b[i]]) % MODULO1;
windowHash2 = (windowHash2 * BASE + trans[(int)b[i]]) % MODULO2;
}
times = 0;
for(; i < m; i++){
//printf("%d: %lld %lld %lld %lld\n", i-n, windowHash1, ahash1, windowHash2, ahash2);
if(windowHash1 == ahash1 && windowHash2 == ahash2){
pos[times++] = i-n;
}
windowHash1 = ((windowHash1 + MODULO1 - powerBase1*trans[(int)b[i-n]]%MODULO1)%MODULO1 * BASE + trans[(int)b[i]])%MODULO1;
windowHash2 = ((windowHash2 + MODULO2 - powerBase2*trans[(int)b[i-n]]%MODULO2)%MODULO2 * BASE + trans[(int)b[i]])%MODULO2;
}
//printf("%d: %lld %lld %lld %lld\n", i-n, windowHash1, ahash1, windowHash2, ahash2);
if(windowHash1 == ahash1 && windowHash2 == ahash2){
pos[times++] = i-n;
}
out = fopen("strmatch.out", "w");
fprintf(out, "%d\n", times);
for(i = 0; i < (times > 1000 ? 1000 : times); i++)
fprintf(out, "%d ", pos[i]);
fprintf(out, "\n");
fclose(out);
}
int main(){
preGen();
readSir();
displayAp();
return 0;
}
/*
ABA
CABBCABABAB
*/