哈希 kmp trie树
哈希
定义
hash方式
hash公式
单hash方法
双hash方法
获取子串的hash
代码
#include<bits/stdc++.h>
using namespace std;
char s1[1000010],s2[1000010];
unsigned h2[1000010],p2[1000010];
unsigned long long h1[1000010],p1[1000010];
unsigned g1(int l,int r)
{return h1[r]-h1[l-1]*p1[r-l+1];
}
unsigned g2(int l,int r)
{return h2[r]-h2[l-1]*p2[r-l+1];
}
int main()
{int t;cin>>t;p1[0]=1;p2[0]=1;for(int i=1;i<=1000000;i++){p1[i]=p1[i-1]*13331;p2[i]=p2[i-1]*13331;}while(t--){cin>>s1>>s2;int len1=strlen(s1); int len2=strlen(s2); unsigned h1a=0,h2a=0;for(int i=0;i<len1;i++){h1a=h1a*13331+s1[i];h2a=h2a*13331+s1[i]; }for(int i=0;i<len2;i++){h1[i+1]=h1[i]*13331+s2[i];h2[i+1]=h2[i]*13331+s2[i]; }int ans=0;for(int i=1;i+len1-1<=len2;i++){if(g1(i,i+len1-1)==h1a&&g2(i,i+len1-1)==h2a){ans++;}}cout<<ans<<endl;}return 0;
}
kmp
kmp优化
代码
#include<bits/stdc++.h>
using namespace std;
int nxt[400010];
bool ans[400010];
int main()
{string s;while(cin>>s){memset(nxt,-1,sizeof(nxt));memset(ans,0,sizeof(ans));int m=s.size();for(int i=1,j=-1;i<m;i++){while(j>-1&&s[i]!=s[j+1]) {j=nxt[j];}if(s[i]==s[j + 1]){j++;} nxt[i]=j;}int x=nxt[m-1];ans[m]=1;while(x!=-1){ans[x+1]=1;x=nxt[x];}if(s[0]==s[m-1]){ans[1]=1;}for(int i=1;i<=m;i++){if(ans[i]==1){cout<<i<<" "; }}cout<<endl;}return 0;
}
trie 树
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int Trie[2010000][50],tot=1,ed[2010000];
string ss[2000100];
void insert(string str)
{int len=str.size(),p=1;for(int i=0;i<len;i++){int ch=str[i]-'0';if(Trie[p][ch]==0){tot++;Trie[p][ch]=tot;}ed[p]=0;p=Trie[p][ch];}if(ed[p]!=0){ed[p]=1;}
}
int search(string str)
{int len=str.size(),p=1;for(int i=0;i<len;i++){p = Trie[p][str[i]-'0'];if(p==0){return 0;}}return ed[p];
}
int main()
{int t;cin>>t;while(t--){cin>>n;memset(ed,2,sizeof(ed));for(int i=1;i<=n;i++){string s;cin>>s;insert(s);ss[i]=s;}for(int i=1;i<=n;i++){if(search(ss[i])==0){cout<<"NO"<<endl;break;}if(i==n){cout<<"YES"<<endl;}}}return 0;
}