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

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

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

#include <stdio.h>#include <string.h>#define MAXN 1000#define BASE 26#define MOD 1000000007char 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为字符串的长度。