字符串算法
1.hash
字符串哈希，可以理解为将字符串映射到一个整数的方法。
给每个字符串分配一个标识符。这个标识符应该尽量满足，相同的字符串有相同的标识符，不同的字符串有不同的标识符。
表达式为： 
模板题：P3370 【模板】字符串哈希
给定 N个字符（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感，请求出 N个字符串中共有多少个不同的字符串。
其中计算字符串的哈希值时，以进制的方式求出十进制下的哈希值
code:
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
int prime=233317;
ull mod=212370440130137957ll;
ull has(char s[]){
int len=strlen(s);
ull ans=0;
for (int i=0;i<len;i++)
ans=(ans*base+(ull)s[i])%mod;
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
a[i]=has(s);
}
sort(a+1,a+n+1);
for(int i=1;i<n;i++){
if(a[i]!=a[i+1])
ans++;
}
printf("%d",ans);
}
另外，有时可以预处理字符串的每个前缀的哈希值来快速计算出每个子串的哈希值：Hash(S[l - r]) = Hash(r)-Hash(l-1)*P^r-l+1
在字符串l - r中，只要减去1 - l - 1对答案的贡献就可以求出。因为在原来字符串的1 - l - 1所乘的P的次幂值时不一样的，所以需要子串再乘上P^r-l+1
有些时候朴素的哈希会被卡，需要双哈希，其实只要设两个base进制就可以了，然后只要两个进制的哈希值都相同就相等了，复制一遍就行了
P4391 [BOI2009]Radio Transmission 无线传输
这道题需要判断循环节
然后代码只有根据上述的预处理前缀的哈希值枚举即可
#include<bits/stdc++.h>
#define N 1000001
#define ull unsigned long long
using namespace std;
const int Bs = 13331;
int n;char S[N];
ull H[N],base[N];
ull to_hash(int l,int r){
return H[r]-H[l-1]*base[r-l+1];
}
int main(){
scanf("%d%s",&n,S+1);
base[0] = 1;
for(int i = 1 ; i <= n ; ++i){
H[i] = H[i-1]*Bs+S[i];
base[i] = base[i-1]*Bs;
}
for(int i = 1 ; i <= n ; ++i){
if(to_hash(1+i,n)==to_hash(1,n-i)){
printf("%d\n",i);
return 0;
}
}
}
P5018 [NOIP2018 普及组] 对称二叉树
给定大小为n的二叉树。询问其中有多少个子树对称我们称一棵树对称，当且仅当将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。
可以用类似先序遍历的方法，但碍于结构的限制必须将没有没有子节点的填上0
然后就可以按照2种遍历方法，一种先左再右，另一种先有再左，得出2个字符串，然后计算每个子树区间的哈希值，相等即可行，取最大值为答案
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 3;
const int MAXM = 2e6 + 3;
int n;
typedef unsigned int u32;
typedef unsigned long long u64;
const u64 BASE = 13331;
u64 H1[MAXM], P[MAXM], H2[MAXM];
u64 get1(int l, int r){
return H1[r] - H1[l - 1] * P[r - l + 1];
}
u64 get2(int l, int r){
return H2[r] - H2[l - 1] * P[r - l + 1];
}
int L[MAXN], R[MAXN], S[MAXN], W[MAXN];
int S1[MAXN], T1[MAXN];
int S2[MAXN], T2[MAXN];
int A[MAXM], B[MAXM], a, b;
void dfs1(int u){
if(u == 0) A[++ a] = 0; else {
S[u] = 1;
A[++ a] = W[u], S1[u] = a;
dfs1(L[u]), dfs1(R[u]);
T1[u] = a, S[u] += S[L[u]] + S[R[u]];
}
}
void dfs2(int u){
if(u == 0) B[++ b] = 0; else {
B[++ b] = W[u], S2[u] = b;
dfs2(R[u]), dfs2(L[u]);
T2[u] = b;
}
}
int main(){
scanf("%d", &n), P[0] = 1;
for(int i = 1;i <= n;++ i) scanf("%d", &W[i]);
for(int i = 1;i <= n;++ i){
scanf("%d%d", &L[i], &R[i]);
if(L[i] == -1) L[i] = 0;
if(R[i] == -1) R[i] = 0;
}
dfs1(1), dfs2(1);
for(int i = 1;i <= a;++ i)
H1[i] = H1[i - 1] * BASE + A[i],
H2[i] = H2[i - 1] * BASE + B[i],
P[i] = P[i - 1] * BASE;
int ans = 0;
for(int i = 1;i <= n;++ i){
u64 h1 = get1(S1[i], T1[i]);
u64 h2 = get2(S2[i], T2[i]);
if(h1 == h2) ans = max(ans, S[i]);
}
printf("%d\n", ans);
return 0;
}