字符串基础:hash,kmp,trie
2022/9/3 23:22:45
本文主要是介绍字符串基础:hash,kmp,trie,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
三个很基础的板子放到一块。发现原来没有位置放了于是现开一个。
- Hash
hash的思想是把一个字符串拍成一个数存储,这样就能快速比较两个字符串是否相同。
大概的方法:
- 我们选取一个合适的进制数(比如131这样的质数)和一个较大的模数。
- 将这个字符串看作一个p进制数(因为每个字符都是有数字大小的)
- 如果这个数过大就取个模。
具体的实现很简单。
void gethash(){ int len=strlen(s+1);p[0]=1; for(int i=1;i<=strlen(s+1);i++){ p[i]=1ll*p[i-1]*prime%mod; hs[i]=(1ll*hs[i-1]*prime+s[i])%mod; } } int gethash(int l,int r){ return (hs[r]-1ll*hs[l-1]*p[r-l+1]%mod+mod)%mod; }
2.kmp(看毛片)
大概是一个不断跳失配指针的\(O(n)\)字符串匹配算法。举个例子,我们要求字符串s在字符串t中的所有出现位置。
首先我们要求出s的失配指针。首先我们定义border是即是s的前缀又是s的后缀(当然不能是s自己)的最长串。
我们可以通过暴力跳的方式求出s的所有border位置。具体地说,让s与自己匹配,如果失配就跳到当前的border指针上,直到匹配或者跳空。
匹配同样暴力跳。
void getnxt(char s[]){ int n=strlen(s+1); nxt[1]=0; for(int i=2,j=0;i<=n;i++){ while(j&&s[i]!=s[j+1])j=nxt[j];//失配 跳指针 if(s[i]==s[j+1])j++;//匹配到 更新指针位置 nxt[i]=j; } } void search(char s[],char t[]){ int n=strlen(s+1),m=strlen(t+1),ans=0; for(int i=1,j=0;i<=m;i++){ while(j&&t[i]!=s[j+1])j=nxt[j];//同样的 匹配时如果失配就跳指针 if(t[i]==s[j+1])j++; f[i]=j;//匹配到就更新最长匹配s的多少长度的前缀 if(j==n)ans[++ans[0]]=i; } }
然后是trie。这个也很简单,按照前缀的顺序搞棵树出来。这个不太好说。上图的话比较简洁,但是我应该不至于这个都搞个图。
void ins(char s[]){ int p=0,len=strlen(s); for(int i=0;i<len;i++){ if(!trie[p][s[i]-'a']){ trie[p][s[i]-'a']=++cnt;//如果当前节点没有这个字母就新建节点 } p=trie[p][s[i]-'a'];//往儿子跳 }cnt[p]++;//标记一下结尾 } int search(char s[]){ int p=0,len=strlen(s); for(int i=0;i<len;i++){ if(!trie[p][s[i]-'a'])return 0; p=trie[p][s[i]-'a'];//同样暴力从树上往下跳 } return cnt[p]; }
trie的另一个应用:01trie。
我们发现(不管是谁发现的反正我没发现)trie的性质可以让它很好地维护异或最大值这种东西。具体地说,我们把int变量拆成31个二进制位扔到trie上。然后每次求异或最大值的时候从上往下跳,有不同跳不同。
void ins(int x){ int now=0; for(int i=30;i>=0;i--){ int w=(x>>i)&1; if(!trie[now][w])trie[now][w]=++cnt;//把当前位拆开上树 now=trie[now][w]; } } int query(int x){ int now=0,ans=0; for(int i=30;i>=0;i--){ int w=(x>>i)&1;ans<<=1; if(trie[now][!w]){ now=trie[now][!w]; ans+=!w;//如果有不同就不同 }else{ now=trie[now][w]; ans+=w; } } return ans; }
这篇关于字符串基础:hash,kmp,trie的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?