ACM POJ 1200

ACM POJ 1200

 

#include
#include

#define Max 16000000
int hash[Max] = { 0 };
int ascii[128];

int rabin_karp(int sizeOfAlphabet, int lengthOfSubstr, char *text) {
    int res = 0, E, count = 1,n = strlen(text);
    int key = 0;
    int i;
    for (i = 1, E = 1; i < lengthOfSubstr; i++)
        E *= sizeOfAlphabet;
   
    memset(ascii, 0, sizeof(ascii));
    while (text[i]) {
        if (!ascii[text[i]])
            ascii[text[i]] = ++key;
        i++;
        if (key == sizeOfAlphabet)
            break;
    }
   
    for (i = 0; i < lengthOfSubstr; i++)
        res = (sizeOfAlphabet * res + ascii[text[i]]);
    hash[res] = 1;
   
    for (i = 0; i < n - lengthOfSubstr; i++) {
        res = sizeOfAlphabet * (res - (ascii[text[i]]) * E) + (ascii[text[i + lengthOfSubstr]]);
        if (!hash[res])
            hash[res] = 1, count++;
    }
    return count;
}
char s[20000000];
int main() {
    int nc, length;
 //freopen("input.txt","r",stdin);
    scanf("%d%d%s", &length, &nc, &s);
    printf("%d", rabin_karp(nc, length, s));
    return 0;
}