简介：
做hdu4300看到的题解，除了kmp还可以用字符串hash做
模板：
1 typedef unsigned long long ull; 2 const int maxn=100000+10; 3 const ull base = 163; 4 char s[maxn],t[maxn]; 5 ull h1[maxn],h2[maxn]; 6 ull p[maxn]; 7 void init(){ ///处理hash值 8 p[0] = 1; 9 h1[0] = h2[0]=0; 10 int n = strlen(s+1); ///字符串从1开始读 11 for(int i = 1; i <=100000; i ++) p[i] =p[i-1] * base; 12 for(int i = 1; i <=n; i ++) hash[i] = hash[i - 1] * base + (s[i] - ‘a‘); 13 } 14 ull geth(int l, int r, ull g[]){///取出g里l - r里面的字符串的hash值 15 return g[r] - g[l - 1] * p[r - l + 1]; 16 }
字符串hash：
1 #include<bits/stdc++.h> 2 #define numm ch-48 3 #define pd putchar(‘ ‘) 4 #define pn putchar(‘\n‘) 5 #define pb push_back 6 #define debug(args...) cout<<#args<<"->"<<args<<endl 7 #define bug cout<<"************" 8 using namespace std; 9 template <typename T> 10 void read(T &res) { 11 bool flag=false;char ch; 12 while(!isdigit(ch=getchar())) (ch==‘-‘)&&(flag=true); 13 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 14 flag&&(res=-res); 15 } 16 template <typename T> 17 void write(T x) { 18 if(x<0) putchar(‘-‘),x=-x; 19 if(x>9) write(x/10); 20 putchar(x%10+‘0‘); 21 } 22 typedef long long ll; 23 typedef unsigned long long ull; 24 typedef long double ld; 25 const int maxn=100000+10; 26 const int maxm=1000+10; 27 const int inf=0x3f3f3f3f; 28 const int mod=1e9+7; 29 const ull base = 163; 30 char s[maxn],t[maxn]; 31 ull h1[maxn],h2[maxn]; 32 ull p[maxn]; 33 void init(){ ///处理hash值 34 p[0] = 1; 35 h1[0] = h2[0]=0; 36 int n = strlen(s+1); ///字符串从1开始读 37 for(int i = 1; i <=100000; i ++) p[i] =p[i-1] * base; 38 // for(int i = 1; i <=n; i ++) hash[i] = hash[i - 1] * base + (s[i] - ‘a‘); 39 } 40 ull geth(int l, int r, ull g[]){///取出g里l - r里面的字符串的hash值 41 return g[r] - g[l - 1] * p[r - l + 1]; 42 } 43 int main() 44 { 45 init(); 46 int _; 47 read(_); 48 char str[30]; 49 while(_--) { 50 map<char,char>mp; 51 scanf("%s%s",str,s+1); 52 for(int i=0;i<26;i++) 53 mp[str[i]]=i+‘a‘; 54 int lenstr=strlen(str),lens=strlen(s+1); 55 for(int i=1;i<=lens;i++) 56 t[i]=mp[s[i]]; 57 for(int i=1;i<=lens;i++) { 58 h1[i]=h1[i-1]*base+(s[i]-‘a‘); 59 h2[i]=h2[i-1]*base+(t[i]-‘a‘); 60 } 61 int lent=strlen(t+1); 62 int a=lens/2+lens%2,pos=0; 63 for(int i=a;i<=lens;i++) { 64 int l=geth(1,lens-i,h2); 65 int r=geth(i+1,lens,h1); 66 if(l==r) { 67 pos=i; 68 break; 69 } 70 } 71 cout<<s+1; 72 if((pos<<1)!=lens) { 73 for(int i=lens-pos+1;i<=pos;i++) 74 putchar(t[i]); 75 } 76 pn; 77 } 78 return 0; 79 }
KMP：
1 #include<bits/stdc++.h> 2 #define numm ch-48 3 #define pd putchar(‘ ‘) 4 #define pn putchar(‘\n‘) 5 #define pb push_back 6 #define debug(args...) cout<<#args<<"->"<<args<<endl 7 #define bug cout<<"************" 8 using namespace std; 9 template <typename T> 10 void read(T &res) { 11 bool flag=false;char ch; 12 while(!isdigit(ch=getchar())) (ch==‘-‘)&&(flag=true); 13 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 14 flag&&(res=-res); 15 } 16 template <typename T> 17 void write(T x) { 18 if(x<0) putchar(‘-‘),x=-x; 19 if(x>9) write(x/10); 20 putchar(x%10+‘0‘); 21 } 22 typedef long long ll; 23 typedef long double ld; 24 const int maxn=100000+10; 25 const int maxm=1000+10; 26 const int inf=0x3f3f3f3f; 27 const int mod=1e9+7; 28 char s[maxn],t[maxn]; 29 int net[maxn]; 30 void getnext(char t[],int len) { 31 int i=0,j=-1; 32 net[0]=-1; 33 while(i<len) { 34 if(j==-1||t[i]==t[j]) { 35 i++,j++; 36 net[i]=j; 37 } 38 else j=net[j]; 39 } 40 } 41 int KMP(int lens,int lent){ 42 int j=0,i=lens/2+lens%2; 43 while(i<lens&&j<lent) { 44 if(j==-1||s[i]==t[j]) 45 i++,j++; 46 else j=net[j]; 47 } 48 return j; 49 } 50 int main() 51 { 52 int _; 53 read(_); 54 char str[30]; 55 while(_--) { 56 map<char,char>mp; 57 scanf("%s%s",str,s); 58 for(int i=0;i<26;i++) 59 mp[str[i]]=i+‘a‘; 60 int lenstr=strlen(str),lens=strlen(s); 61 for(int i=0;i<lens;i++) 62 t[i]=mp[s[i]]; 63 int lent=strlen(t); 64 getnext(t,lent); 65 int len=KMP(lens,lent); 66 cout<<s; 67 if((len<<1)!=lenstr) { 68 for(int i=len;i<lens-len;i++) 69 putchar(t[i]); 70 } 71 pn; 72 } 73 return 0; 74 }
原文：https://www.cnblogs.com/wuliking/p/11679586.html
