C语言中回文哈希的实现与应用

回文哈希是一种用于判断字符串是否为回文的方法，它利用了哈希值的特性来快速判断字符串是否对称。

实现回文哈希的方法如下：

#include 
#include 

#define MAXN 1000
#define BASE 26
#define MOD 1000000007

char str[MAXN];
long long hash[MAXN], pow_base[MAXN];

void init() {
    pow_base[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pow_base[i] = pow_base[i - 1] * BASE % MOD;
    }
}

void calc_hash() {
    int len = strlen(str);
    hash[0] = str[0] - 'a' + 1;
    for (int i = 1; i < len; i++) {
        hash[i] = (hash[i - 1] * BASE + str[i] - 'a' + 1) % MOD;
    }
}

long long get_hash(int l, int r) {
    if (l == 0) {
        return hash[r];
    }
    return ((hash[r] - hash[l - 1] * pow_base[r - l + 1]) % MOD + MOD) % MOD;
}

int is_palindrome(int l, int r) {
    return get_hash(l, r) == get_hash(r, l);
}

int main() {
    init();
    scanf("%s", str);
    calc_hash();
    int len = strlen(str);
    int l = 0, r = len - 1;
    while (l < r) {
        if (is_palindrome(l, r)) {
            l++;
            r--;
        } else {
            printf("Not a palindrome.\n");
            return 0;
        }
    }
    printf("It's a palindrome.\n");
    return 0;
}

在这段代码中，我们首先定义了一些常量，包括字符串的最大长度MAXN，进制BASE和模数MOD。然后定义了全局变量str用于存储输入的字符串，hash用于存储字符串的哈希值，pow_base用于存储进制的幂次。

接着我们实现了init函数用于初始化pow_base数组，calc_hash函数用于计算字符串的哈希值，get_hash函数用于获取字符串的子串哈希值，is_palindrome函数用于判断字符串的子串是否为回文。

最后在main函数中，我们首先调用init函数初始化数组，然后输入字符串并计算哈希值。接着我们使用双指针法遍历字符串，判断每个字符是否满足回文的条件，如果不满足则输出“Not a palindrome.”，否则输出“It’s a palindrome.”。

回文哈希可以应用于判断字符串是否为回文，或者用于解决一些和回文相关的问题，如查找最长回文子串等。其时间复杂度为O(N)，其中N为字符串的长度。