字符串
字符串哈希
通过求解字符串前缀的哈希值的方式，可以比较字符串内任意字串的相等情况。首先需要把每个字符映射成数字，是什么无所谓（因为字符不好计算哈希值呀），然后类似于计算前缀和的方式，这里是计算h[i]表示前i个字符的哈希值。然后把要计算的每个前缀字符串看作是一个P进制的数（用于求解哈希值的），然后最终结果要映射的0~Qn-1的范围内，也就是要mod Q。对于P的经验值为131或者13331，Q一般是264（此算法我们默认哈希不会产生冲突，不像前面的数值哈希会产生冲突）
通过求出的字符串前缀哈希值，可以用于判断字符串中子串的情况，99.99%的情况不会产生冲突（意思是说子串的哈希值不会冲突）。
求解l~r范围内的子串的哈希值，由于每一位都是有权重的，不可以直接通过前缀哈希值相减获得，需要考虑到权值。具体可以自己推，挺简单的（具体见代码）。
//计算字符串前缀哈希值
//应为求出的哈希值最终结果要映射的0~Q^n-1^的范围内，也就是要mod Q，这里用了一个巧妙的方法，就是用
//unsigned long long（64位）来存储哈希值，溢出后相当于mod 2^64
typedef unsigned long long ULL;
ULL h[N],p[N];//h[N]存字符串前缀哈希值,p[N]用于存P的某次方
const int P=131;//把字符传看作P进制的数
//和前缀和计算类似，这里字符串的下标也从1开始
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=h[i-1]*P+str[i];
p[i]=p[i-1]*P;
}
//获得某字符串的哈希值
ULL get(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
KMP
串的模式匹配
-
BF算法(暴力算法)
-
求next的算法(关键代码):
//求next的过程 默认字符串的下标是从1开始的
//ne数组记录的是，在失配后，应该从模式串的什么位置开始匹配
void get_next(){
ne[1]=0;
int i=1,j=0;
while(i<=n){
if(j==0 || p[i]==p[j]) ne[++i]=++j;//求解next[i+1]的值
else j=ne[j];
}
}
//kmp匹配
void kmp(){
for(int i=1,j=1;i<=m;){
if(j==0 || s[i]==p[j]){
if(j==n){
cout<<i-n<<" ";
j=ne[j];
}else{
i++;
j++;
}
}else j=ne[j];
}
}
Manacher算法（马拉车）
manacher算法用于求解字符串中的最长回文子串。时间复杂度为O(N)。
计算位置i的回文半径图解
通过区间[l,r]之间的对称性，将位置i对称到已经计算出回文半径的位置l+r-i。
/*
为了避免在讨论回文子串的时候分奇偶，所以在原字符串中间隔插入'#'，这样可以使得新字符串的长度都为奇数。
s[N]为构造的新字符串。
d[N]数组维护以某个位置为中心的最长回文半径(包括中心)
[l,r]用来维护一个加速盒子(基于回文子串的对称性)，利用先前求过的d值来更新要求的d[i]。
最长回文子串长度=最长回文半径-1
*/
int k=0;
//构造新字符串
//s[0]='$'作为哨兵，为边界
s[k++]='$',s[k++]='#';
for(int i=0;i<a.size();i++){
s[k++]=a[i],s[k++]='#';
}
//manacher算法
d[1]=1;
int ans=0;
for(int i=2,l=1,r=1;i<=k-1;i++){
//加速盒子的左端点就是某个点最长可以覆盖的回文半径
//如果要求的中点i在加速盒子范围内，基于回文子串的对称性，就可以求解出d[i]=min(d[r-i+l],r-i+1);
if(i<=r)d[i]=min(d[l+r-i],r-i+1);
//计算超出加速盒子的部分就需要暴力向两端移动判断一下
while(s[i-d[i]]==s[i+d[i]])d[i]++;
//更新加速盒子边界
if(i+d[i]-1>r)r=i+d[i]-1,l=i-d[i]+1;
ans=max(ans,d[i]-1) ;
}
字符串哈希+二分求解最长回文子串
时间复杂度O(NlogN)
最外层循环依然是枚举所有回文子串的中心点（时间复杂度为O(n)），内层循环通过二分的方式寻找最大的回文子串半径(包括本身)。注意：这里能用二分是因为答案满足二分的条件，能把集合分为连个部分，一边是满足条件的(是回文子串)，另外一遍是不满足条件的(不是回文子串)，二分的时间复杂度为O(logn)。判断是否为回文子串可以通过字符串哈希的方式，时间复杂度为O(1)
char s[N*2];
int cnt;
int d[N*2];
ULL hl[N*2],hr[N*2];
ULL p[N*2];
//获得字符串的哈希值
ULL get_hash(ULL* h,int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
//二分判断条件
bool check(int i,int mid){
if(get_hash(hl,i-mid+1,i+mid-1)==get_hash(hr,cnt-1-(i+mid-1)+1,cnt-1-(i-mid+1)+1))return true;
return false;
}
s[cnt++]='$',s[cnt++]='#';
for(int i=0;i<t.size();i++){
s[cnt++]=t[i],s[cnt++]='#';
}
//正着求字符串hash
hl[0]=1,p[0]=1;
for(int i=1;i<=cnt-1;i++){
hl[i]=hl[i-1]*P+s[i];
p[i]=p[i-1]*P;
}
//逆着求字符串hash
hr[0]=1;
for(int i=1;i<=cnt-1;i++){
hr[i]=hr[i-1]*P+s[cnt-i];
}
//枚举中心点
int res=0;
for(int i=1;i<=cnt-1;i++){
//二分回文串半径
int l=1,r=min(i,cnt-i);
while(l<r){
int mid=l+r+1>>1;
if(check(i,mid))l=mid;
else r=mid-1;
}
d[i]=l;
res=max(res,d[i]-1);
}