C語(yǔ)言中回文哈希的實(shí)現(xiàn)與應(yīng)用

小樊
82
2024-04-26 17:22:03

回文哈希是一種用于判斷字符串是否為回文的方法，它利用了哈希值的特性來(lái)快速判斷字符串是否對(duì)稱。

實(shí)現(xiàn)回文哈希的方法如下：

#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;
}

在這段代碼中，我們首先定義了一些常量，包括字符串的最大長(zhǎng)度MAXN，進(jìn)制BASE和模數(shù)MOD。然后定義了全局變量str用于存儲(chǔ)輸入的字符串，hash用于存儲(chǔ)字符串的哈希值，pow_base用于存儲(chǔ)進(jìn)制的冪次。

接著我們實(shí)現(xiàn)了init函數(shù)用于初始化pow_base數(shù)組，calc_hash函數(shù)用于計(jì)算字符串的哈希值，get_hash函數(shù)用于獲取字符串的子串哈希值，is_palindrome函數(shù)用于判斷字符串的子串是否為回文。

最后在main函數(shù)中，我們首先調(diào)用init函數(shù)初始化數(shù)組，然后輸入字符串并計(jì)算哈希值。接著我們使用雙指針?lè)ū闅v字符串，判斷每個(gè)字符是否滿足回文的條件，如果不滿足則輸出“Not a palindrome.”，否則輸出“It’s a palindrome.”。

回文哈?？梢詰?yīng)用于判斷字符串是否為回文，或者用于解決一些和回文相關(guān)的問(wèn)題，如查找最長(zhǎng)回文子串等。其時(shí)間復(fù)雜度為O(N)，其中N為字符串的長(zhǎng)度。

0 踩