知识点

KMP 算法知识点讲解&应用
Hash 的进阶概念&相关题目
朴素的回文算法
中心扩展回文算法
Manacher 的相关知识&相关题目

KMP

主串(目标串): 简单来说就是被搜索的字符串，一般来说就是那个长的。
模式串：被匹配，是查找的目标。
算法目标：字符串中的模式定位问题，简单来说就是查找子串，在主串中查找匹配模式串。这一类的算法，又被我们称为模式匹配算法。

对于正确性，BF算法确实是毫无疑问，没有任何问题。但是对于效率上面的算法，确实非常低劣。

而我们将会使用 KMP 算法解决这种低效回退的问题。

KMP 算法的核心思想是，利用已经匹配过的这一部分有效的信息，保持主串位置 i 的值不变，去修改模式串的位置 j 的值。

即 KMP 算法就是告诉我们这个 j 该如何去改变。

在讲 Next 数组之前，我们先来讨论一下前后缀的概念。

字符串前后缀：

**· 前缀：**符号串左部的任意子串（或者说是字符串的任意首部），在 KMP 算法中使用的是“真”前缀，即不包含自己前缀。

简单记忆方式：前缀要找除了自己，且从头开始的所有子串。

**· 后缀：**符号串右部的任意子串（或者说是字符串的任意尾部），在 KMP 算法中使用的是“真”后缀，即不包含自己后缀。

简单记忆方式：前缀要找除了自己，且以最后一个字符结尾的所有子串。

· 举例：

字符串	真前缀	真后缀
a	无	无
ab	a	b
aba	a,ab	a,ba
abaa	a,ab,aba	a,aa,baa
abaab	a,ab,aba,abaa	b,ab,aab,baab
abaabc	a, ab,aba,abaa,abaab	c,bc,abc,aabc,baabc
abaabca	a, ab,aba,abaa,abaab,abaabc	a,ca,bca,abca,aabca,baabca

这部分知识会在大学本科编译原理一门课中学习，不必深究。

求 Next 数组前，我们还要去了解一下最长公共前后缀，他的长度对于 KMP 的 Next 数组的计算有着紧密的联系。

最长公共前后缀：

字符串	真前缀	真后缀	最长公共真前后缀
a	无	无	无
ab	a	b	无
aba	a,ab	a,ba	a
abaa	a,ab,aba	a,aa,baa	a
abaab	a,ab,aba,abaa	b,ab,aab,baab	ab
abaabc	a,ab,aba,abaa,abaab	c,bc,abc,aabc,baabc	无
abaabca	a,ab,aba,abaa,abaaab,abaabc	a,ca,bca,abca,aabca,baabca	a

后面的文中将真省略，大家注意。

如果设模式串 P = "abaabca" ,那我们可以得到以某个位置结尾的子串的最长公共前后缀长度。

字符串	结尾	最长公共前后缀长度	最长公共前后缀
a*	a	0	无
ab*	b	0	无
aba*	a	1	a
abaa*	a	1	a
abaab*	b	2	ab
abaabc*	c	0	无
abaabca	a	1	a

我们可以得出以下表格：

结尾	a	b	a	a	b	c	a
最长公共前后缀长度	0	0	1	1	2	0	1

对于 Next 数组将整体向右移动一位后，在左侧补-1。

结尾	a	b	a	a	b	c	a
Next	-1	0	0	1	1	2	0

next数组求解：

先求最长公共前后缀长度maxl
maxl后移一位放入next数组中，前面补-1
next数组每位加一

nextval数组（找不同）求解：

Next 数组的含义：

对于模式串"abaabca"而言

出现这种从第 1 位就匹配出错的情况，即使通过人工我们不能找到任何优化方式，于是只能将模式串右移。

恰好模式串的 -1 的位置正好置于主串的 i 位置，这就是 next 的第一位补-1 的原因。

我们再看第二种情况，部分匹配成功的情况。

仍对于模式串"abaabca"而言：

设主串为"abaaefaged",那么会有：

在主串的 i=4 位置，模式串 j=4 的位置发生了不匹配。

我们通过最优人工移动可以得到：

恰好与主串 i 位置对应的值是模式串的 1 号位置。

那么与我们计算出的 Next 的数组值相同。

重点来了，我们说一下为什么可以这么神奇！！！

原因：

由于我们通过 next 数组计算，而 next 数组来源于最长公共前后缀的长度，那么为什么最长公共前后缀就能计算出，转移目标呢？

假设某个字符串 s 的最长共前后缀为 X="abcd…",那么这个字符串一定是一下结构，开头是 X 结尾是 X 中间可能会有重叠，匹配到 s 的最后一个字符失败后，那我们知道 X 肯定是匹配成功了，因为 X 不包含最后一个字符。

既然我们知道 X 匹配成功，那么我们一定知道，在主串中一定是从 i 位置开始且一定有一个 X 与模式串中的 X 匹配成功。

如下,点为省略号：

        	i
T=........X.......
S=        X.......
          j

而我们又已知,字符串 s 一定有一个后缀 X，那么我们直接用 s 的后缀 X 去匹配主串的 X，且 X 是最长公共前后缀，那么我们就完成了最优的转移。

当 s 是模式串的从头开始的子串时，就可以得到从某一个字符不匹配时的转移情况。

KMP算法思路&代码：

基本原理已经讲清楚了，我们开始说 KMP 算法。

KMP 算法框架和 BF 大致相似，根据上面的分析，对于字符串的比对我们分为三种。

T[i] == P[j] 的情况此时，两字符相同应该继续比对所以:i=i+1j=j+1
T[i]!=P[j] 的情况此时，两字符不相同，j 应该根据 next 数组进行转移，所以:j=next[j]
j=-1 的情况因为，j=next[j],且 next 第一位为 -1 即出现了第一位就匹配失败的情况，那我们应该做的是，是的模式串的开头向后移动，即:j=j+1那么 j 对应 i 的位置也变成了 i+1 所以：i=i+1那么与情况 1 相同，我们一同考虑。

**!!!!!!**至此，KMP 算法整体思路完成。

我们可以得到以下** KMP 的模板**：

void Getnext(string p)
{
    int pLen = p.size();

    next[0] = -1;

    int k = -1;

    int j = 0;

    while (j < pLen - 1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

#include <bits/stdc++.h>
using namespace std;


string T = "ABCDEFG";
string P = "FG";


int nextt[100005];


void Getnext(string p)
{
    int pLen = p.size();
    nextt[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        // p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            nextt[j] = k;
        }
        else
        {
            k = nextt[k];
        }
    }
}


int KMP(int tStart, string s, string p)
{
    int i = 0;


    int j = 0;


    int sLen = s.size();


    int pLen = p.size();


    while (i < sLen && j < pLen)
    {
        // ①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if (j == -1 || s[i] == p[j])
        {
            i++; // 继续对下一个字符比较
            j++; // 模式串向右滑动
        }


        else
        {
            j = nextt[j];
            // ②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = nextt[j]
            // nextt[j]即为j所对应的nextt值
        }
    }
    if (j == pLen)
        return (i - j); // 主串中存在该模式返回下标号


    else
        return -1; // 主串中不存在该模式
}


int main()
{
    Getnext(P);


    cout << KMP(0, T, P);
}

Practice

题目解析：

这个题目，乍一看是求前缀，有的同学就会想到，我们先把前缀求出来。

比如样例：abb 的前缀是 a ab abb，然后用依次执行 KMP 去检测这些前缀有没有在主串 S 中出现即可。

但是，我们了解 KMP 的原理后可以得知，我们每次都是在找到最后一个不匹配的字符就会移动。已知第 j 个字符不匹配，那么前 0 到 j-1 个字符都是匹配的，0 到 j-1 个字符正好是 j 个，恰好是前缀的长度。此时我们只要记录下最大的 j 即可。

#include <iostream>
using namespace std;


int nextt[1000005];
int maxx = 0;
void Getnextt(string p)
{
    int pLen = p.size();
    nextt[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        // p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            nextt[j] = k;
            maxx = max(maxx, nextt[j]);
        }
        else
        {
            k = nextt[k];
            maxx = max(maxx, nextt[k]);
        }
    }
}
int KMP(int tStart, string s, string p)
{
    int i = 0;


    int j = 0;


    int sLen = s.size();


    int pLen = p.size();


    while (i < sLen && j < pLen)
    {
        // ①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if (j == -1 || s[i] == p[j])
        {
            i++; // 继续对下一个字符比较
            j++; // 模式串向右滑动
        }


        else
        {
            j = nextt[j];
            // ②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = nexttt[j]
            // nexttt[j]即为j所对应的nexttt值
        }
        maxx = max(maxx, j);
    }
    if (j == pLen)
        return (i - j); // 主串中存在该模式返回下标号


    else
        return -1; // 主串中不存在该模式
}


int main()
{


    string S, T;
    cin >> S >> T;


    Getnextt(T);
    KMP(0, S, T);
    cout << maxx << endl;
}

Hash算法

Hash 算法则可以帮助我们判断是否有这个元素，虽然功能简单，但是其 O(1) 时间复杂度是具有高性能的。 Hash 是通过在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。相比普通的查找算法来说，仅仅在比较的环节，就会大大减少查找或映射所需要的时间。

以下主要解释两个字符串之间的关系与其 Hash 值的关系。

字符串 Hash 计算

算法竞赛中特别常用的字符串映射成数字的方式。

实现原理：

将字符串中的每一个字母都看做是一个数字（例：从 a-z ，视为 1-26 ）；
选取两个合适的互质常数 b 和 h，其中 h 要尽可能的大一点，为了降低冲突的概率。b 常用 131，h 常用 1e9+7。

这里我们需要设置公共溢出区所以，我们需要随便找一个 string 数组能开出来的数字，这里选取 999983

由于我们这次不去做映射，所有不需要开判断数组或者计数数组，那么我们就不需要考虑数组能否开出来的情况。

Hash 素数 h 的选取：

由于 1e9+7 这些年被用烂了，部分出题人会在这里卡一下，因为我们是不做冲突处理的，因为当取模的数字很大时冲突的概率很低，我们认为不会冲突。但是部分出题人会根据质数 P 故意制造冲突的数据，所以我们最好不使用 1e9+7。

Hash_Table

https://planetmath.org/goodhashtableprimes

在设计一个好的散列配置的过程中，有一个散列表大小的素数列表是很有帮助的。

下面就是这样一个列表。它具有以下特性：

列表中的每个数字都是素数
每个数字略小于前一个数字的两倍
每个数字都尽可能远离最近的两个 2 的幂

对哈希表使用素数是一个好主意，因为它可以最大限度地减少哈希表中的聚类。第（2）项很好，因为它方便面对扩展数据增长哈希表。据称，第 (3) 项已被证明在实践中产生了特别好的结果。

这是列表：

lwr	upr	%err	prime
2^5	2^6	10.416667	53
2^6	2^7	1.0416670	97
2^7	2^8	0.520833	193
2^8	2^9	1.302083	389
2^9	2^10	0.130208	769
2^10	2^11	0.455729	1543
2^11	2^12	0.227865	3079
2^12	2^13	0.113932	6151
2^13	2^14	0.008138	12289
2^14	2^15	0.069173	24593
2^15	2^16	0.010173	49157
2^16	2^17	0.013224	98317
2^17	2^18	0.002543	196613
2^18	2^19	0.006358	393241
2^19	2^20	0.000128	786433
2^20	2^21	0.000318	1572869
2^21	2^22	0.000350	3145739
2^22	2^23	0.000207	6291469
2^23	2^24	0.000040	12582917
2^24	2^25	0.000075	25165843
2^25	2^26	0.000010	50331653
2^26	2^27	0.000023	100663319
2^27	2^28	0.000009	201326611
2^28	2^29	0.000001	402653189
2^29	2^30	0.000011	805306457
2^30	2^31	0.000000	1610612741

这些列依次是 2 的下界幂、2 的上界幂、素数与前两者的最优中间的相对偏差（以百分比表示），最后是素数本身。

显然这张表的设计满足了以下条件：

列表中的每个数字都是素数
每个数字略小于前一个数字的两倍
每个数字都尽可能远离最近的两个 2 的幂

第二条，目的是，为了能够更好地扩展 Hash 表。

而我们更多的是为了竞赛，所以我们也不需要对 Hash 表进行扩展，一开始开的容量满足要求，那么就可以直接使用，如果我们所需求的容量大于题目给的，那无论使用哪种方式最后都会大于题目给定，所以第二条并不适合竞赛。所有引用该 Hash 表的同志，也没见他们写了动态 Hash 表，笔者认为这张 Hash 表并不是很适合竞赛。

第三条，已被证明在实践中产生了特别好的结果。这一条是可以保留的，此文章发表在 planetmath 具有一定的学术性，所以也利用这一条。

笔者也做出了一张表格，笔者经过多次测试发现冲突率也满足要求。

lwr	upr	prime
2^5	2^6	53
2^6	2^7	101
2^7	2^8	193
2^8	2^9	389
2^9	2^10	769
2^10	2^11	1531
2^11	2^12	3061
2^12	2^13	6113
2^13	2^14	12253
2^14	2^15	24379
2^15	2^16	48883
2^16	2^17	97787
2^17	2^18	195677
2^18	2^19	391627
2^19	2^20	783259
2^20	2^21	1566401
2^21	2^22	3133987
2^22	2^23	6269119
2^23	2^24	12538073
2^24	2^25	25082363
2^25	2^26	50170979
2^26	2^27	100353503
2^27	2^28	200730139
2^28	2^29	401498927
2^29	2^30	803081491

由于 2^20 内的 P 冲突率太高，我们建议大家从 2^26 开始，即很小的数据也要让他对较大的数字取模，甚至大家可以从 2^28 开始挑选质数 P。

之前我们在 Hash 表那一章讲的时候我们没有给出其他的 P 值，在这里我们给出 P 值的表格作为前面知识的补充。

敲好本节课程也需要用到，我们学习一下，并学会打表方法，在比赛时记不住也可以自己手敲代码打表。对于上面质数的求解，我们给出以下打表方法。

注意：仅限于打表求出来后使用，切忌在题目中打表，时间太久，会超时。

Hash_table_opt#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>


// 素数筛法处理
using namespace std;


const unsigned int maxx = 2147483648;


// 欧式筛法，bitset 优化版
bitset<maxx> notPrime;


void getPrimes(int n)
{
    for (int i = 2; i * i <= n; i++)
    {
        if (!notPrime[i])
        {
            for (int j = i * i; j <= n; j += i)
                notPrime[j] = 1;
        }
    }
}


int main()
{
    unsigned int topNum = 2;


    for (int i = 1; i < 30; i++)
    {
        topNum = topNum << 1;
    }


    topNum -= 1;
    // cout<<topNum;
    getPrimes(topNum);


    cout << 1;


    // for(int i=2; i<=topNum; i++) cout<<notPrime[topNum]<<" ";


    for (int i = 5; i < 30; i++)
    {


        // 上界
        unsigned int Up = pow(2, i + 1);


        // 下界
        unsigned int Down = pow(2, i);
        cout << "| 2^" << i << "|";
        cout << "2^" << i + 1 << "|";


        vector<int> vPrime;
        vPrime.clear();


        for (int j = Up; j >= Down; j--)
        {


            if (!notPrime[j])
            {
                vPrime.push_back(j);
            }
        }
        cout << vPrime[(vPrime.size() - 1) / 2] << "|" << endl;
    }
}

复习哈希函数：

处理方式：

C 代表一个字符串，用 C =c1 c2 c3 c4..cm 表示该字符串，其中 ci 表示从前向后数的第 i 个字符；
方括号[ ]内的表达式是将 C 当做 b 进制数来处理，b 是基数；
关于对 h 取模，若 b、h 有公因子，那么不同的字符串取余之后的结果发生冲突的几率将大大大增加（冲突：不同的字符串但会有相同的 hash 值）。
计算上一步 H(C) 的过程是递归实现的：H(C,k)为前 k 个字符构成的字符串的哈希值， $H(C,k+1)= H( C , k ) * b+c( k+1 );$

还是那个例子：

int Hx(string s)
{
    int n = s.size();
    
    for (int i = 0; i < n; i++)
    {
        sum1 = sum1 * 131 % h + (s[i] - 'a' + 1) % h;
    }

    return (sum1 + h) % h;
}

带大家回顾了以下旧知识，也补充了知识点。现在我们来学习以下新的知识。

请大家一定记住：

$H(C,k+1)= H( C , k ) * b+c( k+1 );$

H(C,k)为前 k 个字符构成的字符串的哈希值，这个公式，这个公式对整体的推导起决定性的作用。

假设存在一个字符串：

那他的子串 S'= S( i+1 , j ) 的 Hash 值为：

$H(S')=H( S , j ) - H(S, i ) * b^{(j-i)}$

带入得：

$H(S')=[s1 ∗ b^{(j-1)}+...+sj]-[s1 * b^{(i-1)}+...+si]*b^{(j-i)}$

化简得：

$H(S')=[s1 ∗ b^{(j-1)}+...+sj]-[s1 * b^{(j-1)}+...+si*b^{(j-i)}]$

最终得：

既然是子串 S(i,j) 那么实际计算 hash 值得时候

Si 是第 0 个所以 i=0 带入可得：

因此 S 的子串 S'= S( i+1 , j ) 的 Hash 值为：

$H(S')=H( S , j ) - H(S, i ) * b^{(j-i)}$

的结论得证！

补充：

众所周知，hash 算法有时会产生冲突，但是在一般比赛中用字符串 Hash 产生冲突的概率是很小的，如果真的不放心可以采用“双哈希”来避免冲突。
我们预处理除 b^1 到 b^n 的值。
在实现算法时，可以利用 32 位或 64 位无符号整数计算哈希值，此时 h=2^32 或 h=2^64，通过自然溢出省去求模运算。(因为无符号整数，大于最大值后会以最大值+1 为模数取模)

由于 Java 和 Python 中没有无符号整形我们进行模拟。

Practice

斤斤计较的小 Z

难度: 简单

标签: 字符串Hash

题目描述:

小 Z 同学没天都喜欢斤斤计较，今天他又跟字符串杠起来了。他看到了两个字符串 s1，s2 ，他想知道 S1 在 S2 中出现了多少次。现在给出两个串 S1，S 2(只有大写字母)，求 S1 在 S2 中出现了多少次。

数据范围字符串长度len, 1<len(s1)<len(s2)<10^6

字符取值大写字母和小写字母

输入描述：

共输入两行

第一行为 S1

第二行为 S2

输出描述：

输出 S1 在 S2 中出现了多少次

输入输出样例：

● 样例 1：Input：
              LQYK
              LQYK
        output：
              1
● 样例 2：Input：
              LQYKLQYKLQYKLQYK
              LQYK
        output：
              4
● 样例 3：Input：
              AADSDFGADSWADADADD
              WSAD
        output：
              0

题目解析：

将匹配串 S1 的哈希值求出来，再将母串 S 2 的哈希值数组求出来，根据结论 $H(C’) = H(C,k+n) - H(C,k)*b^n$ 求出与匹配串长度相等的母串子串的哈希值，与匹配串 S1 的哈希值比较，如果相等，答案+1。

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

typedef unsigned long long ull;

const int base = 131;



const int maxn = 1e6 + 5;

char sTemp1[maxn], sTemp2[maxn];

ull power[maxn];

string s1, s2;

ull hash2[maxn];

int n;

ull hash1;

int ans=0;

void init() {
    power[0] = 1;
    for (int i = 1; i <= 10002; i++)//预处理base^n
        power[i] = power[i - 1] * base;
}

int main() {

    init();

    scanf("%s", &sTemp1);
    scanf("%s", &sTemp2);

    s1 = sTemp1;
    s2 = sTemp2;

    //强烈建议这样读取字符串，节省时间

    int len1 = s1.size();
    int len2 = s2.size();

    for (int i = 1; i <= len1; ++i)
        hash1 = hash1 * base + (ull)(s1[i - 1] - 'A' + 1);

    hash2[0] = (s2[0] - 'A' + 1);

    for (int i = 1; i <= len2; ++i)
        hash2[i] = hash2[i - 1] * base + (ull)(s2[i - 1] - 'A' + 1);
    for (int i = 0; i <= len2 - len1; ++i) {
        ull hash = hash2[i + len1] - hash2[i] * power[len1];
        if (hash == hash1)
            ans++;
    }
    printf("%d\n", ans);

    return 0;
}

Manacher

在讲 Manacher 算法之前，我们的要先补充几个概念。

回文：

回文，汉语词语，指汉语中的回文语法，即把相同的词汇或句子，在下文中调换位置或颠倒过来，产生首尾回环的情况，叫做回文，也叫回环。

这是在中文语境下的，在英文环境中，叫做 Palindromic。

回文字符串(Palindromic String):

“回文串”是一个正读和反读都一样的字符串。如“viooiv”、“nexttexn”、“12321”、“WWWWWW”、“锅盖盖锅” 等。

回文子串：

一个字符串，他的子串大家都学过，我们之前的都了解过。如果一个字符串的子串是回文结构的，那么我们称之为回文子串。

最长回文子串：

字符串的最长回文子串，是指一个字符串中包含的最长的回文子串。如果在 "abcdeffgh" 包含的最长回文子串就是 "ff"。

朴素的回文算法：

我们先说一下普通的，大家求解最长回文串的方式。

对于最长回文串问题，我们最简单朴素的方法就是：

    1. 找到字符串 S 的所有子串 S'[]
    2. 然后遍历所有的子串 S'[],然后分别判断每个子串 S'[i] 是否回文。
    3. 字符串 S 共计$  n^2 $ 个子串，对于每个子串的验证是$ O(N) $ 所以整体复杂度是 $ O(N^3) $

#include <iostream>
using namespace std;

string s;

//判断是否回文

int isPal(int start,int end) //s的[start,end)的左闭右开区间
{
    int len=end-start;

    //偶数abba型,对称轴位置没有字母
    if(len%2==0)
    {

        int mid=start+(len/2);
        //找到mid的长度，只需要枚举一半即可。


        int i=start;
        //枚举起点

        int pal=end-1;
        //对应的回文的位置

        for(;i<=mid;i++,pal--)
        // i----->    向中间枚举    <------pal
        {

            if(s[i]!=s[pal])
                return -1;
            //有一处不回文，那么整体不回文，返回-1 代表不回文。

        }

//        cout<<len<<":"<<s.substr(start,len)<<endl;
        return len;
        //都回文那么整体回文，返回长度
    }

    //奇数aba型,对称轴位置有字母
    else
    {
        int mid=start+((len-1)/2);
        //找到mid的长度，只需要枚举一半即可,因为对称轴字母必然和自己对称所以可以不考虑


        int i=start;
        //枚举起点

        int pal=end-1;
        //对应的回文的位置

        for(;i<=mid;i++,pal--)
            // i----->    向中间枚举    <------pal
        {

            if(s[i]!=s[pal])
                return -1;
            //有一处不回文，那么整体不回文，返回-1 代表不回文。

        }
//        cout<<len<<":"<<s.substr(start,len)<<endl;
        return len;
        //都回文那么整体回文，返回长度
    }

}

//分解子串,并记录最长回文子串的长度

int subString()
{
    int maxn=1;
    //最短是1，比如a,b,c,d

    int len=s.size();//字符串长度

    for(int i=0;i<=len;i++)
    //枚举左闭端点
    {
        for(int j=i+1;j<=len;j++)
        //枚举右开端点
        {
//            cout<<s.substr(i,j-i)<<":";
            maxn=max(maxn, isPal(i,j));
//            puts("");
        }
    }
    return  maxn;
}

int main()
{



    cin>>s;


   //cout<<isPal(0,s.size());

    cout<<subString()<<endl;
}V

中心扩展法：

我们知道，回文串都是回文的，即所见即所得，既然回文它就有必然有一个对称中心。我们通过枚举对称中心的位置，进行扩展那么，就可以完成对回文字符串的判定。那我们就要执行以下操作：

1. 枚举中心位置 n 个字符和 n-1 个字符中间位置（偶数回文）
2. 以中心位置向两侧延伸，直至不是回文位置
3. 在枚举过程中统计最大的回文子串

#include <iostream>
using namespace std;
string s;


// 中心扩展法：
// 我们知道，回文串都是回文的，即所见即所得，既然回文它就有必然有一个对称中心。
// 我们通过枚举对称中心的位置，进行扩展那么，就可以完成对回文字符串的判定。
// 那我们就要执行以下操作：
// 枚举中心位置 n 个字符和 n-1 个字符中间位置（偶数回文）
// 以中心位置向两侧延伸，直至不是回文位置
// 在枚举过程中统计最大的回文子串


int expand(int l, int r)
{


    // 字符串扩展


    while (l >= 0 && r < s.length() && s[l] == s[r])
    // 如果回文处相同且不超过字符串的范围：
    {


        l--;
        r++;


        // 扩展
    }


    return r - l - 1;
    // 不能扩展返回最大长度
}


int Palindromic()
{
    if (s == "" || s.length() == 0)
    {
        return 0;
    }
    int maxn = 1;


    for (int i = 0; i < s.length(); i++)
    {
        int l1 = expand(i, i);     // 以字符作为中心点扩展
        int l2 = expand(i, i + 1); // 以字符间隙作为中心点扩展
        int len = max(l1, l2);


        maxn = max(maxn, len);
    }
    return maxn;
}


int main()
{
    cin >> s;


    cout << Palindromic() << endl;
}

对于中心扩展的回文算法，我们分析一下：

由于长度的奇偶性问题，不同的对称轴要分两类情况讨论分析.
有多次重复计算。如 cbcacbc 第一个 cbc 被计算过，第二个 cbc 也被计算过，一整个个 cbcabcbc 又被计算了一次。

于是 Manacher 的提出解决了以上问题。

改进分析：

对于问题”由于长度的奇偶性问题，不同的对称轴要分两类情况讨论分析“(解决对称轴的变化带来的复杂性)：通过对于字符串的预处理解决长度奇偶性带来的对称轴位置变化。
- 预处理方式：
  - 在所有字符间隙中和开头结尾插入同样的符号，一般使用#（$），当然只要不影响题目本身的符号（即不在原来的字符串中出现）都是可以的。
  - 这样可以使的所有的字符串都是奇数串，即消除了奇偶变化所带来的的差异化处理。
- 形如： + abcd -> $a$ b $c$ d $</font> + <font style="color:red;">abba</font> -> <font style="color:red;">$ a $b$ b $a$ + abcba -> $a$ b $c$ b $a$
  - 我们可以看到是字符串回文的性质没有发生改变，发生改变的只有回文串的长度。
  - 即再求出最长的回文子串后再减去所有的 # 数量就可以得到长度。
- 为了防止越界处理等，我们一般在开头和结尾在缀上两个不一样的字符。
- 形如： + abcd -> @#a#b#c#d#% + abba -> @#a#b#b#a#% + abcba -> @#a#b#c#b#a#%
解决重复计算的问题：为了解决这个问题，我们要引入几个辅助变量。
- Max：最远标记距离
  - 即目前最靠右的回文串的右端点
- Pos：最远中心点
  - 即目前最靠右的回文串的中心点
- length[i]：回文半径
  - 以 i 为中心扩展的回文串的半径，恰好比不扩展的原字符串的直径大 1.

算法实现过程：

假设前 i-1 个字符已经被处理过，那么我们将处理第 i 个字符，则会有下面的情况。

设 j 为 i 关于 Pos 的对称点

j = 2 * pos - i

MaxL 为 Max 关于 Pos 的对称点。

MaxL = 2*Pos - Max

i < Max 的情况：
- 当以 j 为中心的回文串被 Max 串包含：此时我们知道，由于 Max 串关于 Pos 回文，所以以 j 为对称轴回文的串，也会在 Pos 右侧以 i 为对称轴出现。所以我们可以得知 length[i] = length [j] = length[ 2*Pos -i ]。
- 当以 j 为中心的回文串范围超出 Max 串：即 j-length[j] < MaxL 时。
- 我们不能保证超出 MaxL 左侧的字符也会在 Max 的右侧出现，所以我们只能最大限度的考虑 i 的回文半径，那就是 Max - i
- 我们可以综合考虑二者，因为他们之间肯定存在一个大小关系，如果是第一种情况，那么有 length[2Pos -i ] ≤ Max -i , 如果是第二种情况，那么就有个 length[2Pos -i ] >= Max -i 的情况。
- 因此我们直接使用最短那个即可。
- 即当 i < Max 时：length[i]=min(length[2*pos-i],Max-i);
i>=Max 的情况此时的 i 并不能参考 j 的处理情况，也无其他规律可循，只能按照朴素的算法处理。

由此马拉车的代码水到渠成的就写出来了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5;
string s;
int length[maxn * 2];
int manacher(string p)
{
    int le = p.size();
    for (int i = 0; i < le; i++)
    {
        s[i * 2 + 2] = p[i];
        s[i * 2 + 1] = '+';
    }
    s[0] = '@', s[le * 2 + 1] = '%'; // 选取不可能出现的字符即可。


    // 预处理字符串成为一个奇数串；
    int Max = 0, pos = 0, ans = 0;
    le = 2 * le + 1;
    for (int i = 1; i <= le; i++)
    {
        if (Max > i)
        {
            length[i] = min(length[2 * pos - i], Max - i);
        }
        else
            length[i] = 1;
        while (s[i - length[i]] == s[i + length[i]])
            length[i]++;
        ans = max(length[i], ans);
        if (i + length[i] > Max)
        {
            Max = length[i] + i;
            pos = i;
        }
    }
    return ans - 1;
}
int main()
{


    string in;
    cin >> in;
    cout << manacher(in) << endl;
    return 0;
}

Practice:

最长回文子串

难度: 简单

标签: Manacher

链接：https://www.lanqiao.cn/problems/1225/learning/

题目描述:

给定一个字符串 S，请你求出 S 的最长回文子串。

输入描述：

输入仅一行，包含一个字符串 S。保证 S 只包含小写字母、大写字母、数字。

长度不超过10^5

输出描述：

输入输出样例：

Input：aa1ABA1b

output：5

题目解析：

这个题目虽然是个模板题，但数据量较大，注意输入输出时间复杂度，字符处理的复杂度，在部分地方做了修改，大家要学习一下，直接使用模板是不能通过的。

 #include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
char a[maxn];
string s;
int length[maxn*2];
int manacher(string p)
{
    int le=p.size();

    //插入分隔符，奇数化
    for(int i=0;i<le;i++)
    {
        s[i*2+1]='#';
        s[i*2+2]=p[i];

    }
    s[le*2+1]='#';


    // 前后缀，不用考虑边界处理就能不越界

    s[0]='@',s[le*2+2]='%';//选取不可能出现的字符即可。


    int Max=0,pos=0,ans=0;
    le=2*le+1;
    for(int i=1;i<=le;i++)
    {
        if(Max>i)
        {
            length[i]=min(length[2*pos-i],Max-i);
        }
        else  length[i]=1;

        //尝试扩展
        while(s[i-length[i]]==s[i+length[i]])
            length[i]++;

        ans =max(length[i],ans);
        if(i+length[i]>Max)
        {
            Max=length[i]+i;
            pos=i;
        }
    }
    return ans-1;
}
int main()
{

    string in;
    //cin>>in; 从现在开始大量数据输入，拒绝使用cin
    scanf("%s",a);

    //char 数组可以直接赋值给string 字符串
    in=a;

    /*
     string 不能直接转char ，可以使用循环，但不能忘记结尾的空字符。

     */

    cout<<manacher(in)<<endl;

    return 0;
}