专注于网站营销服务,大型门户网站开发公司,长沙做网站优化的公司,首钢建设工资网站作者 | 程序员小灰来源 | 程序员小灰#xff08;ID#xff1a;chengxuyuanxiaohui #xff09;————— 第二天 —————什么意思呢#xff1f;让我们来举一个例子#xff1a;在上图中#xff0c;字符串B是A的子串#xff0c;B第一次在A中出现的位置下标是2#… 作者 | 程序员小灰来源 | 程序员小灰IDchengxuyuanxiaohui ————— 第二天 —————什么意思呢让我们来举一个例子在上图中字符串B是A的子串B第一次在A中出现的位置下标是2字符串的首位下标是0所以返回 2。我们再看另一个例子在上图中字符串B在A中并不存在所以返回 -1。为了统一概念在后文中我们把字符串A称为主串把字符串B称为模式串。小灰的想法简单粗暴让我们用下面的例子来演示一下第一轮我们从主串的首位开始把主串和模式串的字符逐个比较显然主串的首位字符是a模式串的首位字符是b两者并不匹配。第二轮我们把模式串后移一位从主串的第二位开始把主串和模式串的字符逐个比较主串的第二位字符是b模式串的第二位字符也是b两者匹配继续比较主串的第三位字符是b模式串的第三位字符也是c两者并不匹配。第三轮我们把模式串再次后移一位从主串的第三位开始把主串和模式串的字符逐个比较主串的第三位字符是b模式串的第三位字符也是b两者匹配继续比较主串的第四位字符是c模式串的第四位字符也是c两者匹配继续比较主串的第五位字符是e模式串的第五位字符也是e两者匹配比较完成由此得到结果模式串 bce 是主串 abbcefgh 的子串在主串第一次出现的位置下标是 2以上就是小灰想出的解决方案这个算法有一个名字叫做BF算法是Brute Force暴力算法的缩写。上图的情况在每一轮进行字符匹配时模式串的前三个字符a都和主串中的字符相匹配一直检查到模式串最后一个字符b才发现不匹配这样一来两个字符串在每一轮都需要白白比较4次显然非常浪费。假设主串的长度是m模式串的长度是n那么在这种极端情况下BF算法的最坏时间复杂度是Omn。————————————比较哈希值是什么意思呢用过哈希表的朋友们都知道每一个字符串都可以通过某种哈希算法转换成一个整型数这个整型数就是hashcodehashcode hashstring显然相对于逐个字符比较两个字符串仅比较两个字符串的hashcode要容易得多。给定主串和模式串如下假定字符串只包含26个小写字母第一步我们需要生成模式串的hashcode。生成hashcode的算法多种多样比如按位相加这是最简单的方法我们可以把a当做1b当做2c当做3......然后把字符串的所有字符相加相加结果就是它的hashcode。bce 2 3 5 10但是这个算法虽然简单却很可能产生hash冲突比如bce、bec、cbe的hashcode是一样的。转换成26进制数既然字符串只包含26个小写字母那么我们可以把每一个字符串当成一个26进制数来计算。bce 2*(26^2) 3*26 5 1435这样做的好处是大幅减少了hash冲突缺点是计算量较大而且有可能出现超出整型范围的情况需要对计算结果进行取模。为了方便演示后续我们采用的是按位相加的hash算法所以bce的hashcode是10第二步生成主串当中第一个等长子串的hashcode。由于主串通常要长于模式串把整个主串转化成hashcode是没有意义的只有比较主串当中和模式串等长的子串才有意义。因此我们首先生成主串中第一个和模式串等长的子串hashcode即abb 1 2 2 5第三步比较两个hashcode。显然510说明模式串和第一个子串不匹配我们继续下一轮比较。第四步生成主串当中第二个等长子串的hashcode。bbc 2 2 3 7第五步比较两个hashcode。显然710说明模式串和第二个子串不匹配我们继续下一轮比较。第六步生成主串当中第三个等长子串的hashcode。bce 2 3 5 10第七步比较两个hashcode。显然10 10两个hash值相等这是否说明两个字符串也相等呢别高兴的太早由于存在hash冲突的可能我们还需要进一步验证。第八步逐个字符比较两字符串。hashcode的比较只是初步验证之后我们还需要像BF算法那样对两个字符串逐个字符比较最终判断出两个字符串匹配。最后得出结论模式串bce是主串abbcefgh的子串第一次出现的下标是2。什么意思呢让我们再来看一个例子上图中我已知子串abbcefg的hashcode是26那么如何计算下一个子串也就是bbcefgd的hashcode呢我们没有必要把子串的字符重新进行累加运算而是可以采用一个更简单的方法。由于新子串的前面少了一个a后面多了一个d所以新hashcode 旧hashcode - 1 4 26-14 29 再下一个子串bcefgde的计算也是同理新hashcode 旧hashcode - 2 5 29-25 32 public static int rabinKarp(String str, String pattern){
//主串长度
int m str.length();
//模式串的长度
int n pattern.length();
//计算模式串的hash值
int patternCode hash(pattern);
//计算主串当中第一个和模式串等长的子串hash值
int strCode hash(str.substring(0, n));//用模式串的hash值和主串的局部hash值比较。
//如果匹配则进行精确比较如果不匹配计算主串中相邻子串的hash值。
for (int i0; im-n1; i) {
if(strCode patternCode compareString(i, str, pattern)){
return i;
}
//如果不是最后一轮更新主串从i到in的hash值
if(im-n){
strCode nextHash(str, strCode, i, n);
}
}return -1;
}private static int hash(String str){
int hashcode 0;
//这里采用最简单的hashcode计算方式
//把a当做1把b当中2把c当中3.....然后按位相加
for (int i 0; i str.length(); i) {
hashcode str.charAt(i)-a;
}
return hashcode;
}private static int nextHash(String str, int hash, int index, int n){
hash - str.charAt(index)-a;
hash str.charAt(indexn)-a;
return hash;
}private static boolean compareString(int i, String str, String pattern) {
String strSub str.substring(i, ipattern.length());
return strSub.equals(pattern);
}public static void main(String[] args) {
String str aacdesadsdfer;
String pattern adsd;
System.out.println(第一次出现的位置: rabinKarp(str, pattern));
}为了助力对抗疫情减少线下人员流动和聚集CSDN与 PyCon 官方授权的 PyCon中国社区合作举行「Python开发者日」在线系列峰会。通过精彩的技术干货内容、有趣多元化的在线互动活动等让您足不出户便可与大咖学习交流共同渡过抗疫攻坚期。活动咨询可扫描下方二维码加入官方交流群⬇️⬇️⬇️福利扫描添加小编微信备注“姓名公司职位”入驻【CSDN博客】加入【云计算学习交流群】和志同道合的朋友们共同打卡学习推荐阅读大数据抗疫的“洪荒之力”多地政府借力大数据技术多家企业上马大数据产品“云原生全家桶“KubeSphere 如何让企业从容迈进云原生时代为什么说程序员做外包没前途官宣了受疫情影响程序员可免费领这些12 大 AI App 技术创意教你如何在 2020 年赚到钱远程办公绝非远程监控该如何挖掘远程办公的红利真香朕在看了
