字符串 hash 算法求解回文串

VincentFF 2020-02-25 16:50:09
原文地址:https://segmentfault.com/a/1190000021665249

字符串 hash 算法求解回文串

此文以一个题目为例,讲解求解回文串的 hash 字符串解法。
注: 除了 kmp 算法之外,该算法也可用来求解字符串子串问题,此处不论述该问题。

题目

给定一个字符串 S,以及 q 次询问。每次询问给出两个正整数 L,R,你需要回答 S[L~R]是否为回文串。
input
第一行给出字符串 S,|S|<=1e6. 保证字符串仅由小写字母构成。
第二行给出询问次数 q,q<=1e6.
接下来每行给出两个整数 L,R,1<=L,R<=|S|.
output
对于每个询问,若字符串 S 中[L,R]为回文串,输出 YES,否则输出 NO。
测试用例

输入:

abccba
5
1 6
2 5
3 4
1 3
1 1

输出:

YES
YES
YES
NO
YES

解答

一、暴力解法

设置两个指针,前后依次遍历匹配。该方法时间复杂度较高,为 O(n*q),直接上代码,不再赘述。

// 判断字符串s从i到j的子字符串是否为回文串
bool judege(char *s, int i, int j){
    while (i &lt; j)
    {
        if(s[i] != s[j])
            break;
        i++;
        j--;
    }
    return i &gt;= j;
}

二、字符串哈希解法

所谓字符串 hash,就是通过 hash 运算,将原本的字符串的子串计算为一个个可以计算的整数,最后求子串时可直接通过整数计算求得。此方法将计算子串的时间复杂度由 O(n)降为了 O(1)。最后通过将子串的正序 hash 值与逆序 hash 值相比较是否相等,即可评判该子串是否为回文串,大大节省了计算时间,整体时间复杂度下降为 O(n+q)。
下面详细介绍该算法:

生成 hash 序列

为了更加直观的讲解,我们以数字字符串s=&quot;-123456789&quot;为例,用十进制将该字符串生成 hash 序列。为了方便计算 s[0]不存储有效值。
先设置一个数组Hash[10]来存放我们生成的 Hash 序列。Hash[0] = 0, Hash[1] = Hash[0] * 10 + (s[i]-'0'),递归可得Hash[i] = Hash[i-1]*10 + (s[i]-'0')
其中s[i] - '0'是为了将对应的字符计算为其对应的整数,如'5' - '0'计算得整数5
代码如下:

Hash[0] = 0;
for (int i = 1; i &lt; 10; i++)
{
    Hash[i] = Hash[i-1] * 10 + (s[i] - '0');
}

最后生成的 Hash[10]序列如下:
再次强调,Hash[0]是功能位,方便计算,并没有存储字符串&quot;123456789&quot;生成的 hash 值,有效 hash 值从 Hash[1]开始。

0 1 2 3 4 5 6 7 8 9
--- --- --- --- --- --- --- --- --- ---
0 1 12 123 1234 12345 123456 1234567 12345678 123456789

得到了如上的 hash 序列,我们怎么通过该 hash 序列求子串的值呢?
如我们需要求子串&quot;345&quot;的 hash 值,我们只需要通过计算Hash[5] - Hash[2]*10^3即可求得。
所以我们需要求得子串s[l:r]的 hash 值,只需要计算Hash[r] - Hash[l-1]*10^(r-l+1)即可。
计算一个子串的 hash 值只需要 O(1)的时间。

通过字符串 hash 验证回文串

我们已经知道了如何计算字符串的 hash 值,以及如何通过字符串 hash 序列来求解子串。那么如何通过字符串 hash 值来验证回文串呢。
上文讲过回文串验证是通过比较子串的正序 hash 值与逆序 hash 值是否相等来求得的。
如字符串&quot;121&quot;,其正序哈希值为121,逆序 hash 值也为121,所以&quot;121&quot;是回文串。而&quot;123&quot;的正序 hash 值为123,逆序 hash 值为321,所以&quot;123&quot;不是回文串。
所以除了正序Hash[10]序列之外,我们还需要求出一个&quot;-1234546789&quot;的逆序 hash 序列Hash_reverse[10],该求法与以上正序 hash 序列求法相同。

int slen = 9; //字符串长度为9
Hash_reverse[0] = 0;
for (int i = 1; i &lt; 10; i++)
{
    Hash_reverse[i] = Hash_reverse[i-1] * 10 + (s[slen-i+1] - '0');
}

生成的逆序 hash 序列如下:

0 1 2 3 4 5 6 7 8 9
--- --- --- --- --- --- --- --- --- ---
0 9 98 987 9876 98765 987654 9876543 98765432 987654321

现在我们得到了字符串&quot;123456789&quot;的正序与逆序的hash 序列。
要验证子串s[l:r]是否为回文串,只需求得s[l:r]s[r:l]的 hash 值,相比较即可。
举个例子,我们要求字符串s中的第 3 到 5 位(即&quot;345&quot;)是否为回文串,通过Hash[5] - Hash[2]*10^3即可求得&quot;345&quot;的 hash 值345,
Hash_reverse[7]-Hash_reverse[4]*10^3即可求得&quot;345&quot;的逆 hash 值为543
345 != 543,所以&quot;345&quot;不是回文串。
求子串s[l:r]的算法如下:

int hs = Hash[r] - Hash[l-1] * 10^(r-l+1); // s[l:r]的hash值
int hs_reverse = Hash_reverse[slen-l+1] - Hash_reverse[slen-r]*10^(r-l+1);//s[r:l]的hash值
if(hs == hs_reverse)
    printf(&quot;s[l:r]是回文串\n&quot;);
else
    printf(&quot;s[l:r]不是回文串\n&quot;);

至此,字符串hash求解回文串的算法已经介绍完毕。下面是这个题的hash解法的完整代码:

#include &lt;bits/stdc++.h&gt;
using namespace std;

// 通过字符串hash方法来多次求回文串,只需要O(n+q)时间复杂度,暴力解法为O(n*q) //
const unsigned long long int base = 2333; //base表示进制,用一个大质数作为进制减少hash碰撞
const int N = 1e6 + 3;
int Hash[N], Hash_reverse[N], power[N];
char s[N];
int main()
{
    int q, l, r;
    scanf(&quot;%s %d&quot;, s + 1, &amp;q);
    int slen = strlen(s + 1);

    // 初始化hash和逆hash数组, 以及表示base进制位数的power数组
    // 数组从1开始存储字符串和哈希值,Hash[0]为功能位,方便计算
    Hash[0] = 0;
    Hash_reverse[0] = 0;
    power[0] = 1;
    // power存放的是进制位数,方便计算。以十进制为例power[3]即为10^3.
    // 此题我们选的进制是质数2333,power[3]即为2333^3
    for (int i = 1; i &lt; slen + 1; i++)
    {
        power[i] = power[i - 1] * base;
    }
    // 计算字符串的hash值,时间复杂度只需O(n)
    for (int i = 1; i &lt; slen + 1; i++)
    {
        Hash[i] = Hash[i - 1] * base + s[i] - 'a' + 1; // 加1是为了让hash值不为0,如果前面某位hash值为0,将会影响后面hash值的计算

        Hash_reverse[i] = Hash_reverse[i - 1] * base + s[slen - i + 1] - 'a' + 1;
    }

    // 下面通过哈希值来判断回文串,每次判断只需要O(1)时间复杂度
    for (int i = 0; i &lt; q; i++)
    {
        scanf(&quot;%d %d&quot;, &amp;l, &amp;r);
        if ((Hash[r] - Hash[l - 1] * power[r - l + 1]) == (Hash_reverse[slen - l + 1] - Hash_reverse[slen - r] * power[r - l + 1]))
            printf(&quot;YES\n&quot;);
        else
            printf(&quot;NO\n&quot;);
    }

    return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。