字符串哈希
//题目：好文章（双哈希。。学长是x哈希）
#include<stdio.h> #include<math.h> #include<iostream> #include<algorithm> #include<string.h> #include<map> #define ll long long #define base1 13131 #define base2 7327 #define P1 1000000007 #define P2 1000000009 #define inf 0x3f3f3f3f using namespace std; int n,m; ll Hash1[200005]; ll Hash2[200005]; ll pow1[200005]; ll pow2[200005]; struct node{ ll x,y; }; node cc[200005]; char tt[200005]; bool cmp(node a,node b){ if(a.x==a.y)return a.y<b.y; return a.x<b.x; } int main(){ scanf("%d%d",&n,&m); pow1[0]=pow2[0]=1; for(int i=1;i<=n;++i){ pow1[i]=pow1[i-1]*base1%P1; pow2[i]=pow2[i-1]*base2%P2; } scanf("%s",tt+1); for(int i=1;i<=n;++i){ int cc=tt[i]; Hash1[i]=(Hash1[i-1]+cc*pow1[i])%P1; Hash2[i]=(Hash2[i-1]+cc*pow2[i])%P2; } ll c1,c2; ll ans=n-m+1; for(int i=1;i<=n-m+1;++i){ cc[i].x=(Hash1[i+m-1]-Hash1[i-1]+P1)%P1*pow1[n-i-m+1]%P1;//*pow1[m+1]; cc[i].y=(Hash2[i+m-1]-Hash2[i-1]+P2)%P2*pow2[n-i-m+1]%P2;//*pow2[m+1]; } sort(cc+1,cc+n-m+2,cmp); for(int i=2;i<=n-m+1;++i){ if(cc[i].x==cc[i-1].x&&cc[i].y==cc[i-1].y){ ans--; } } printf("%d",ans); return 0; }
树哈希
//地铁问题(树哈希的板题？？？)
#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<vector> #define ll long long #define ull unsigned long long #define base 7397 #define P 1000000007 using namespace std; char A[3005],B[3005]; ull Hash(char *p,int st,int en){ int cnt=0,pos=st+1,ans=131; vector<int>tmp; for(int i=st;i<=en;i++) { if(p[i]=='0')cnt++; else cnt--; if(!cnt){ tmp.push_back(Hash(p,pos,i-1)); pos=i+2; } } sort(tmp.begin(),tmp.end()); for(int i=0;i<tmp.size();i++){ ans=(ans*base^tmp[i])%P; } return ans; } int main(){ int T; scanf("%d",&T) ; while(T--){ scanf("%s",A); scanf("%s",B); int l=strlen(A); int ans1=Hash(A,0,l-1); int ans2=Hash(B,0,l-1); if(ans1==ans2)printf("same "); else printf("different "); } return 0; }