如果要比较字符串是否相等,首先想到的是KMP算法,但是hash更加简洁易于编写,hash的目的是把一串字符转化成一个数字,用数字来比较是否相等。我让mod=912837417 Base=127,防止hash碰撞
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 const LL mod=912837417;
5 const LL Base=127;
6 char T[5000],P[5000];
7 LL lenT,lenP;
8 LL hash[5000];
9 LL base[5000];
10 LL hashP;
11 inline LL query(LL l,LL r){
12 LL ans=(hash[r]-(hash[l-1]*base[r-l+1]))%mod;
13 if(ans<0) ans+=mod;
14 return ans;
15 }
16 int main(){
17 scanf("%s%s",T+1,P+1);
18 lenT=strlen(T+1); lenP=strlen(P+1);
19 base[0]=1;
20 for(int i=1;i<=lenT;i++){
21 base[i]=(base[i-1]*Base)%mod;
22 hash[i]=(hash[i-1]*Base+(LL)(T[i]-'a'+1))%mod;
23 if(i<=lenP) hashP=(hashP*Base+(LL)(P[i]-'a'+1))%mod;
24 }
25 for(int i=1;i<=lenT-lenP+1;i++){
26 LL now=query(i,i+lenP-1);
27 if(now==hashP){
28 cout<<"从第"<<i<<"位开始匹配"<<endl;
29 return 0;
30 }
31 }
32 cout<<"不能匹配"<<endl;
33 return 0;
34 }
原文链接: https://www.cnblogs.com/CXCXCXC/p/4935210.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/224094
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!