判断是否为回文数（Rabin-Karp 字符串哈希算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了判断是否为回文数（Rabin-Karp 字符串哈希算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2083字，纯文字阅读大概需要3分钟。

内容图文

题目：leetcode 214.最短回文数

  给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

      输入: "aacecaaa"

      输出: "aaacecaaa"

示例 2:

      输入: "abcd"

      输出: "dcbabcd"


题目分析：

1. 假定给定字符串s,那么假设s2=s-s[0],则s2的翻转+s一定是一个回文数。如s=abcdcba,则s2=bcdcba，那么reverse(s2.begin(),s2.end())+s=abcdcbabcdcba是回文数；
2. 本题目实际是从左到右找出字符串中的最长回文数字符串，而后将剩余的字符串翻转后加载原字符串前面；
3. 如s="aacecaaa",可以看到"aacecaa"是回文数字符串，那么将剩余的"a"翻转后添加在s前面则得到结果"aaacecaaa"；

回文数判断算法（Rabin-Karp字符串哈希算法）

1. 该算法需要一个base和一个mod,目的是通过base和mod将字符串映射到一个十进制数值上，该数值就是哈希值，而这里的base就相当于十进制里的10（一般要大于字符的最大ASCII码值，这样不会出现进位问题），mod是为了防止字符串过长导致计算出来的数值无法存放，出现内存溢出问题。
2. 当两个字符串的哈希值相同时，当且仅当两个字符串相等。但是在定mod值的时候尽量选的大一点，避免哈希碰撞问题，如mod=13,那么2和15对13进行mod后，值都为2，此时便产生了哈希碰撞问题。
3. 更新规则，将字符串看成base进制的数字，假设字符串为s，指针来到了第i位置，我们把从0到i字符串定义为是s1,从i到0的字符串定义为s2,则:

• s1=Hash(s1[i])=base*Hash(s1[i-1])+ASCII(s[i]);   s2=Hash(s2[i])=Hash(s2[i-1])+base^(i-1)*ASCII(s[i]);

代码：

#include <iostream>
#include<algorithm>
using namespace std;
class solution{
public:
    string shortestPalindrome(string s){
    int base=107,mod=10000017;
    int n=s.size();
    long long left=0,right=0;
    long long base_r=1;
    int best=-1;//解决字符串为空的问题，在best之前的子字符串为回文数字符串
    string add;
    for (int i=0;i<n;i++){
        left=(left*base+s[i])%mod; //对应s1的哈希值计算
        right=(right+s[i]*base_r)%mod; //对应s2的哈希值计算
        if (left==right){best=i;}
        base_r=(base_r*base)%mod;
    }
    add= (best==n-1 ? "" : s.substr(best+1,n));//如果best在s的最后一位，则add为空，否则add为best+1到字符串末尾的子字符串。
    reverse(add.begin(),add.end());
    cout<<"原字符串: "<<s<<endl;
    return add+s;
    }
};
int main()
{
solution f;
cout<<"更新后的回文数字符串:"<<f.shortestPalindrome("aacecaaa")<<endl;
return 0;
}

 

结果截图：

内容总结

以上是互联网集市为您收集整理的判断是否为回文数（Rabin-Karp 字符串哈希算法）全部内容，希望文章能够帮你解决判断是否为回文数（Rabin-Karp 字符串哈希算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---