前言
虽然标题是 Hash ，但本篇文章不会仅仅注重于 Hash 算法。
要求读者的是掌握 Hash 的思想以及简单应用，同时牢固掌握字符串 Hash 。
同时本篇文章也简单讲述了离散化和Manacher（马拉车）算法。
请读者放心食用。
简单介绍
简述
Hash 表又称散列表，是一种基于 链表+哈希函数 实现的算法，与离散化思想类似。
当我们要对若干复杂信息进行统计时，可以用 Hash 函数将其映射到一个简单的、容易维护的值域。
Hash 冲突
因为值域简单，所以容易发生冲突，所以要处理这种冲突情况。
这里仅介绍最常用的拉链法，有兴趣的同学可以自寻百度寻找其它方法。
最常用的方法就是链表存储，就是人们常说的拉链法或链地址法，下图就是简单的存储之后的样子。
离散化
本来没打算讲的，但是既然和 Hash 思想类似，就当做入门吧。
离散化其实就是缩小值域最直接的方法：排序后按编号赋值。（例如 1,30,69,51,5 变成 1,3,5,4,2）
一般离散化有三个步骤：
- 排序。（可以用 sort 实现）
- 去重。（可以用 C++ STL 的 \(unique\) 函数实现）
- 二分查找离散化。（可以用 C++ STL 的 \(lower\)_\(bound\) 函数实现）
给一道例题好好体会：有一个序列a，每次操作给出（l,r），询问a中值在l和r之间的数的和。
代码见下：
int main() {
for (int i = 1; i <= n; ++i)
b[i] = a[i];
sort(b+1, b+n+1);
int m = unique(b+1, b+n+1) - (b+1);
for (int i = 1; i <= n; ++i) {
int v = a[i];
a[i] = lower_bound(b+1, b+m+1, v) - b;
c[a[i]] += v;
}
for (int i = 1; i <= m; ++i)
s[i] = s[i-1] + c[i];
while (q--) {
scanf("%d%d", &l, &r);
l = lower_bound(b+1, b+m+1, l) - b;
r = lower_bound(b+1, b+m+1, r) - b - 1;
printf("%d\n", s[r] - s[l-1]);
}
}
个人认为这就是很基础的 Hash （如果这都理解不了就别学 Hash 了吧）
可以到百度去看看离散化，加深一下理解，对学习 Hash 有帮助。
基本结构
Hash 的基本结构有两个：
- 计算 Hash 函数的值。
- 定位到对应的链表中依次遍历、比较。（基于邻接表实现，不会的自行百度）
当 Hash 函数设计的好的时候，所有元素几乎平均地位于每一个表头，即几乎不产生冲突。
此时查询的期望值是 \(O(1)\) 的。
普通 Hash
简述
在这里，普通 Hash 指的是整数类型的 Hash。 （后面会讲到运用广泛的字符串 Hash 算法）
最直接的思想是设计一个较大的质数 \(P\) ，令 \(Hash(x)=(x\) \(mod\) \(P)+1\) 。（加一是避免有 \(0\) 的产生）
此时所有数值都分布于 \(1\)~\(N\) 之中。
这种 Hash 思想简单，易于实现，这里不做过多的介绍。
例题
简单例题，这里我们定义的 Hash 函数：\(H(a_1,a_2...a_n)=(\sum_{j=1}^{6} a(i,j)+\prod_{j=1}^{6} a(i,j) )mod\) \(P\)。
其中 P 是某个较大的质数，直接上代码吧。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 100010
#define MOD 99991
using namespace std;
int n,a[10],show[N][10],head[N],next[N],tot=0;
bool equal(int x){
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
bool flag=true;
for(int k=0;k<6;k++) if(a[(i+k)%6]!=show[x][(j+k)%6]) flag=false;
if(flag) return true;
flag=true;
for(int k=0;k<06;k++) if(a[(i+k)%6]!=show[x][(j-k+6)%6]) flag=false;
if(flag) return true;
}
}
return false;
}
int H(){
int sum=0;
long long mul=1;
for(int i=0;i<6;i++){
sum=(sum+a[i])%MOD;
mul=(mul*(long long)a[i])%MOD;
}
return (sum+mul)%MOD;
}
bool insert(){
int val=H();
for(int i=head[val];i;i=next[i]){
if(equal(i)) return true;
}
tot++;
for(int i=0;i<6;i++) show[tot][i]=a[i];
next[tot]=head[val];
head[val]=tot;
return false;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=0;j<6;j++) scanf("%d",&a[j]);
if(insert()){printf("Twin snowflakes found.\n");return 0;}
}
printf("No two snowflakes are alike.\n");
return 0;
}
字符串 Hash
简单介绍
下面介绍的是一种可以把任意长度（最好不要太长，一般 \(<=1e6\)）的字符串转变成一个非负整数。
特点：碰撞概率几乎为0。（因此不需要链表结构防止冲突）
核心思想
一般有以下步骤预处理字符串 Hash:
- 首先取一个固定值 \(P\) 并把字符串 \(A\) 当成 \(P\) 进制数。
- 接着将字符串 \(A\) 转化为整数 \(a=1,b=2...,z=26\)。
- 取一个固定值 \(M\) ，求出该 \(P\) 进制数对于 \(M\) 的余数作为 \(Hash(A)\)。
通常我们取 \(P=131/P=13331\) ，此时冲突的概率极低。（一般不会构造数据去卡你，因为很难构造）
通常我们取 \(M=2^{64}\) ，即 \(unsigned\) \(long\) \(long\) 的最大值，所以使用该类型存储 \(Hash(A)\) 。
如果 \(Hash(A)>2^{64}\) 会自动溢出，正好符合取余运算，同时避免了低效的 % 运算。
基本运算
有以下两种运算：
- 已知字符串 \(S\) 的 Hash 值为 \(H(S)\) ，那么在 \(S\) 后面添加一个字符 \(c\) 构成新字符串时：\(H(S+c)=(H(s)*P+value[c])mod\) \(M\)。(其中 \(value[c]=c-'a'+1\))
- 已知字符串 \(S\) 的 Hash 值为 \(H(S)\) ，字符串 \(S+T\) 的 Hash 值为 \(H(S+T)\) 时：\(H(T)=(H(S+T)-H(S)*P^{length(T)})\)。（相当于 \(S\) 在 \(P\) 进制下左移 \(length(T)\) 位然后被 \(H(S+T)\) 减）
举个栗子：\(S="abc",c="d",T="xyz"\) ，则：
- \(S\) 表示的 \(P\) 进制数为 ：1 2 3。（很好理解吧，对应核心思想的 \(step2\)）
- \(H(S)=1*P^2+2*P+3\)。
- \(H(S+c)=1*P^5+2*P^4+3*P+4=H(s)*P+4\)。
- \(S+T\) 表示的 \(P\) 进制数为：1 2 3 24 25 26
- \(H(S+T)=1*P^5+2*P^4+3*P+24*P^2+25*P+26\)
- \(S\) 在 \(P\) 进制下左移 \(length(T)\) 位：1 2 3 0 0 0
- 二者相减就是 \(T\) 的 \(P\) 进制数表示：24 25 26
- \(H(T)=H(S+T)-(1*P^2+2*P+3)*P^3=24*P^2+25*P+26\)。
根据以上两种操作可知，\(O(N)\) 的预处理前缀 Hash 值后，即可 \(O(1)\) 地判断两个字符串是否相同。
前缀和不会我也没办法，自行百度吧
二维字符串 Hash
学过二维前缀和的同学都知道 f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]。
那么二维 Hash 也不过是这样罢了。
不过由于是二维的，我们最好用两个不同的 \(P\) 来 Hash，具体代码长这样。
#define P 131
#define Q 13331
ull f[N][N],pp[N],pq[N];
for(int i=1;i<=N;i++)
pp[i]=pp[i-1]*P,pq[i]=pq[i-1]*Q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=f[i-1][j]*P+f[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=f[i][j-1]*Q+f[i][j];
//计算矩形 (a,b),(c,d) 的 Hash 值为：(a<=c,b<=d)
Hash=f[c][d]-f[a-1][d]*pp[c-a+1]-f[c][b-1]*pq[b-d+1]+f[a-1][b-1]*pp[c-a+1]*pq[b-d+1]
这里引入一道例题加深理解：Matrix 矩阵。
判断若干小矩阵是否是大矩阵的子矩阵。
二维字符串 Hash 轻松解决。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 1010
#define MOD 99991
#define P 131
#define Q 13331
using namespace std;
typedef unsigned long long ull;
int n,m,a,b,cnt=0;
int head[N*N];
ull f[N][N],g[N][N],pp[N],pq[N];
char s[N];
struct Edge{
int nxt;
ull to;
}ed[N*N];
int read(){
int x=0,f=1;char c=getchar();
while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
return x*f;
}
void init(){//输入兼预处理。
pp[0]=pq[0]=1;
for(int i=1;i<=N;i++)
pp[i]=pp[i-1]*P,pq[i]=pq[i-1]*Q;
n=read(),m=read(),a=read(),b=read();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++)
f[i][j]=s[j]-'0';
}
return;
}
int Hash(ull k){return k%MOD+1;}//简单 Hash。
bool search(ull k){//链式查找。
int u=Hash(k);
for(int i=head[u];i;i=ed[i].nxt)
if(k==ed[i].to) return true;
return false;
}
void insert(ull k){//插入。
int now=Hash(k);
if(!search(k))
ed[++cnt].to=k,ed[cnt].nxt=head[now],head[now]=cnt;
return;
}
void pre_work(){//预处理大矩阵的 Hash 值。
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=f[i-1][j]*P+f[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=f[i][j-1]*Q+f[i][j];
for(int i=a;i<=n;i++)
for(int j=b;j<=m;j++){
ull now=f[i][j];
now-=f[i-a][j]*pp[a];
now-=f[i][j-b]*pq[b];
now+=f[i-a][j-b]*pp[a]*pq[b];
insert(now);
}
return;
}
ull work(){//计算小矩阵的 Hash 值。
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
g[i][j]=g[i-1][j]*P+g[i][j];
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
g[i][j]=g[i][j-1]*Q+g[i][j];
return g[a][b];
}
int main(){
init();
pre_work();
int q=read();
while(q--){
for(int i=1;i<=a;i++){
scanf("%s",s+1);
for(int j=1;j<=b;j++)
g[i][j]=s[j]-'0';
}
ull k=work();
if(search(k)) puts("1");
else puts("0");
}
return 0;
}
例题
兔子与兔子
字符串 Hash 模板题，初学者必做。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 1000010
using namespace std;
char s[N];
int m;
unsigned long long f[N],p[N];
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
scanf("%d",&m);
p[0]=1;
for(int i=1;i<=n;i++){
f[i]=f[i-1]*131+(s[i]-'a'+1);
p[i]=p[i-1]*131;
}
for(int i=1;i<=m;i++){
int l1,r1,l2,r2;
scanf("%d %d %d %d",&l1,&r1,&l2,&r2);
if(f[r1]-f[l1-1]*p[r1-l1+1]==f[r2]-f[l2-1]*p[r2-l2+1]) printf("Yes\n");
else printf("No\n");
}
return 0;
}
回文子串的最大长度
这里仅仅讲述 Hash 思想，因为有算法复杂度更优的 \(Manacher\) 算法。
思想就是枚举每个回文子串的中心位置 \(i=1\)~\(N\) ，分情况讨论奇数和偶数长度，
接着二分答案枚举字符串长度，利用字符串 Hash 判断两个字符串是否相同。（需要一个前缀数组和一个后缀数组）
不断刷新 \(ans=min(ans,len)\) ，复杂度 \(O(n\) \(log\) \(n)\) 。
下一段我们将讨论优秀的 \(Manachar\) 算法，可以 \(O(n)\) 解决最长回文子串的问题。
后缀数组
思路是先处理 \(SA[]\) 数组，初始化为 \(SA[i]=i\) 接着以字典序排序。（方法见下）
假设已经排好序了，我们就来求两个字符串的最长公共前缀，同样可以二分答案地去找。
发现可以将其写作函数，返回值为最长公共前缀的长度，那么 \(SA[]\) 数组排序时只需要 return(s[a+len]<s[b+len])
其中 \(a,b\) 为 \(cmp\) 函数的两个参数，\(len\) 是其最长公共前缀的长度，至此本问题得到完美解决。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 300010
using namespace std;
int sa[N],height[N],n;
unsigned long long p[N],H[N];
char s[N];
unsigned long long find(int a,int b){
return (H[b]-H[a-1]*p[b-a+1]);
}
int len(int a,int b){
if(s[a]!=s[b]) return 0;
int l=0,r=n-1-max(a,b);
while(l<r){
int mid=(l+r+1)>>1;
if(find(a,a+mid)==find(b,b+mid) && a+mid<n && b+mid<n)
l=mid;
else r=mid-1;
}
return l+1;
}
bool cmp(int a,int b){
int l=len(a,b);
return s[a+l]<s[b+l];
}
int main(){
scanf("%s",s);
n=strlen(s);
p[0]=1;
H[0]=s[0]-'a'+1;
for(int i=1;i<n;i++){
sa[i]=i;
p[i]=p[i-1]*131;
H[i]=H[i-1]*131+(s[i]-'a'+1);
}
sort(sa,sa+n,cmp);
for(int i=0;i<n;i++) printf("%d ",sa[i]);
printf("\n0 ");
for(int i=1;i<n;i++) printf("%d ",len(sa[i],sa[i-1]));
return 0;
}
Manacher 算法
背景
给定一个字符串，求出其最长回文子串。例如：
- \(s="abcd"\)，最长回文长度为 \(1\)；
- \(s="ababa"\)，最长回文长度为 \(5\)；
- \(s="abccb"\)，最长回文长度为 \(4\)，即 \(bccb\)。
以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为 ，效率很差。
1975 年，一个叫 Manacher 的人发明了一个算法，\(Manacher\) 算法（中文名：马拉车算法）。
下面来看看马拉车算法是如何工作的。
算法过程分析
由于回文分为偶回文（比如 bccb）和奇回文（比如 bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：在字符串首尾，及各字符间各插入一个字符（前提这个字符未出现在串里）。
举个例子：s="abbahopxpo"，转换为s_new="$#a#b#b#a#h#o#p#x#p#o#"。（这里的字符 $ 只是为了防止越界，下面代码会有说明）
如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#p#o#，长度都转换成了奇数。
定义一个辅助数组int p[]，其中p[i]表示以 i 为中心的最长回文的半径，例如：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s_new[i] | $ | # | a | # | b | # | b | # | a | # | h | # | o | # | p | # | x | # | p | # |
| p[i] | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 4 | 1 | 2 | 1 |
经事后提醒发现表格缺少了7以后的部分，并且目前没有好的解决办法，可以自行点击原文链接查看，不过应该不影响阅读
可以看出，p[i] - 1正好是原字符串中最长回文串的长度。
接下来的重点就是求解 p 数组，如下图：
设置两个变量，mx 和 id 。mx 代表以 id 为中心的最长回文的右边界，也就是mx = id + p[id]。
假设我们现在求p[i]，也就是以 i 为中心的最长回文半径，如果i < mx，如上图，那么：
if (i < mx)
p[i] = min(p[2 * id - i], mx - i);
2 * id - i为 i 关于 id 的对称点，即上图的 j 点，而p[j]表示以 j 为中心的最长回文半径，因此我们可以利用p[j]来加快查找。
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char s[1000];
char s_new[2000];
int p[2000];
int Init()
{
int len = strlen(s);
s_new[0] = '$';
s_new[1] = '#';
int j = 2;
for (int i = 0; i < len; i++)
{
s_new[j++] = s[i];
s_new[j++] = '#';
}
s_new[j] = '\0'; // 别忘了哦
return j; // 返回 s_new 的长度
}
int Manacher()
{
int len = Init(); // 取得新字符串长度并完成向 s_new 的转换
int max_len = -1; // 最长回文长度
int id;
int mx = 0;
for (int i = 1; i < len; i++)
{
if (i < mx)
p[i] = min(p[2 * id - i], mx - i); // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
else
p[i] = 1;
while (s_new[i - p[i]] == s_new[i + p[i]]) // 不需边界判断，因为左有'$',右有'\0'
p[i]++;
// 我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，这样才能更有机会执行 if (i < mx)这句代码，从而提高效率
if (mx < i + p[i])
{
id = i;
mx = i + p[i];
}
max_len = max(max_len, p[i] - 1);
}
return max_len;
}
int main()
{
while (printf("请输入字符串：\n"))
{
scanf("%s", s);
printf("最长回文长度为 %d\n\n", Manacher());
}
return 0;
}
算法复杂度分析
文章开头已经提及，Manacher 算法为线性算法，即使最差情况下其时间复杂度亦为\(O(n)\) 。
在进行证明之前，我们还需要更加深入地理解上述算法过程。
根据回文的性质，p[i]的值基于以下三种情况得出：
（1）：j 的回文串有一部分在 id 的之外，如下图：
假设右侧新增的紫色部分是p[i]可以增加的部分，那么根据回文的性质，a 等于 d ，也就是说 id 的回文不仅仅是黑线，而是黑线+两条紫线，矛盾，所以假设不成立，故p[i] = mx - i，不可以再增加一分。
（2）：j 回文串全部在 id 的内部，如下图：
根据代码，此时p[i] = p[j]，那么p[i]还可以更大么？答案亦是不可能！见下图：
假设右侧新增的红色部分是p[i]可以增加的部分，那么根据回文的性质，a 等于 b ，也就是说 j 的回文应该再加上 a 和 b ，矛盾，所以假设不成立，故p[i] = p[j]，也不可以再增加一分。
（3）：j 回文串左端正好与 id 的回文串左端重合，见下图：
根据代码，此时p[i] = p[j]或p[i] = mx - i，并且p[i]还可以继续增加，所以需要
while (s_new[i - p[i]] == s_new[i + p[i]])
p[i]++;
根据（1）（2）（3），很容易推出 Manacher 算法的最坏情况，即为字符串内全是相同字符的时候。在这里我们重点研究 Manacher() 中的 for 语句，推算发现 for 语句内平均访问每个字符 5 次，即时间复杂度为：\(T_{worst}(n)=O(n)\)。
同理，我们也很容易知道最佳情况下的时间复杂度，即字符串内字符各不相同的时候。推算得平均访问每个字符 4 次，即时间复杂度为：\(T_{best}(n)=O(n)\)。
综上，Manacher 算法的时间复杂度为 \(O(n)\)。
以上内容全部转载自原文链接，确实写的很好。
例题
\(Update\) \(2020.3.18\)
新增两道例题，好像多很难的样子 (｡･｀ω´･｡)
例题一
首先这既然关于回文串，就打一遍 \(Manacher\) 的板子。
然后...（\(INF\) 年过去了）
啊，终于想到了，既然每个字符串都可以分为两个回文部分，那么我么就记录下每个串的左右回文串长度。
即：
- \(l[i]\) 代表 \(i\) 位置所在回文串中中心位置最左端的位置。
- \(r[i]\) 代表 \(i\) 位置所在回文串中中心位置最右端的位置。
然后是不是就豁（geng）然（jia）开（mi）朗（mang）了？
具体的解释就看代码注释吧。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 100010
using namespace std;
int p[N*2],n,l[N*2],r[N*2];
char s[N*2],a[N];
int pre_work(){
int len=strlen(a);
s[0]='$';
s[1]='#';
int j=2;
for(int i=0;i<len;i++){
s[j++]=a[i];
s[j++]='#';
}
s[j]='\0';
return j;
}
void manacher(){
n=pre_work();
int id,mx=0;
for(int i=1;i<n;i++){
if(i<mx) p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]]) ++p[i];
if(mx<i+p[i]){
id=i;
mx=i+p[i];
}
r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1);
l[i-p[i]+1]=max(l[i-p[i]+1],p[i]-1);
/**
* l[i]表示以i为左端点的最长的回文串
* r[i]表示以i为右端点的最长的回文串
*
* 对于蒟蒻(我)来讲有点抽象所以我们举一个生动的栗子：
*
* 首先，字符串为ababaccd
*
* 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17
* 插入后变成 #|$|a|$|b|$|a|$|b|$|a |$ |c |$ |c |$ |d |~
*
* 显然i = 4时,hw[4] = 4
* L = 7 = i + hw[4]-1;
* R = 1 = i-hw[4]+1;
* 回文串实际长度=hw[4]-1;
* 所以转移就是: l[i+hw[i]-1]=max(l[i+hw[i]-1],hw[i]-1);
* r[i-hw[i]+1]=max(r[i-hw[i]+1],hw[i]-1);
*
*/
}
}
int main(){
scanf("%s",a);
manacher();
for(int i=n;i>=1;i-=2) r[i]=max(r[i],r[i+2]-2);
for(int i=1;i<=n;i+=2) l[i]=max(l[i],l[i-2]-2);
/**
* 又因为两块不能重叠，所以我们选择'$'作为断点进行枚举
*
* 那么先提出一个困扰蒟蒻我的问题：
*
* Q: 上面不是已经求过了吗，为什么还要递推呢？
*
* A: 上面求出的每个l[i]和r[i]都是在i最大的情况下求的
*
* eg:0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17
* #|$|a|$|b|$|a|$|b|$|a |$ |c |$ |c |$ |d |~
*
* l[3]求出来的是0,但很明显bab是一个回文,l[3]应该等于3
* 这是因为我们在i=6时,hw[i]=6,只更新了l[1]和r[11],因为bab不是i=6的最长回文串所以没有更新
*
* 这时就需要递推把前面的转移过来了：
*
* bab 比 ababa 短两个字符。
* 每一个回文串向后挪动一个 都会少两个字符,所以：
* l[i] = max(l[i], l[i - 2] - 2);
* r[i] = max(r[i], r[i + 2] - 2);
* 我们枚举的是'$'的位置，所以l[i]正推由前一个'$'的位置转移来,r[i]逆推由后面的'$'转移来，每次都会-2回文串长度
*
*/
int ans=0;
for(int i=1;i<=n;i+=2) if(r[i]&&l[i]) ans=max(ans,l[i]+r[i]);
printf("%d\n",ans);
return 0;
}
例题二
NUMOFPAL - Number of Palindromes
相比上一题，这道题的难度就小很多了。
直接就是：
\]
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 1010
using namespace std;
int p[N*2],n,id,mx=0;
char a[N],s[N*2];
int pre_work(){
s[0]='$';
s[1]='#';
int j=2;
for(int i=0;i<strlen(a);i++){
s[j++]=a[i];
s[j++]='#';
}
s[j]='\0';
return j;
}
void manacher(){
n=pre_work();
for(int i=1;i<n;i++){
if(mx>i) p[i]=min(p[id*2-i],mx-i);
else p[i]=1;
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(mx<i+p[i]){
id=i;
mx=i+p[i];
}
}
return;
}
int main(){
scanf("%s",a);
manacher();
int ans=0;
for(int i=0;i<n;i++){
ans+=p[i]/2;
}
printf("%d\n",ans);
return 0;
}
结语
感谢 LZshuing 给了我灵感，以及让我入门 Hash。
感谢 \(Manacher\) 部分作者的优秀文章，再上原文链接。
感谢您的观看，同时这篇文章希望对您有帮助。