回文哈希是一种用于判断字符串是否为回文的方法,它利用了哈希值的特性来快速判断字符串是否对称。
实现回文哈希的方法如下:
#include <stdio.h>
#include <string.h>
#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为字符串的长度。