算法

Manacher(马拉车)算法 引入 若是某个字符串正着表示和反着表示都是一样的，那么我们可以将这个字符串称作回文字符串。例如abba就是一个回文字符串，而字符串abbbc就不是，因为其反着表示的形式为cbbba与原字符串不同。而在一个字符串中可能存在多个满足回文条件的子串，我们一般取长度最长的称做最长回文子串。如在字符串abacdcabad中存在aba，cdc，acdca等满足回文条件的子串，但是并非最长，其最长回文子串为abacdcaba。那么我们如何求一个字符串中的最长回文子串呢？以下以洛谷P3805题为例  例题解析 题目描述 给出一个只由小写英文字符 a,b,c,…y,z 组成的字符串 S ,求 S 中最长回文串的长度 。字符串长度为 n。 输入格式 一行小写英文字符 a,b,c,⋯,y,z 组成的字符串 S。  输出格式 一个整数表示答案。  输入输出样例 输入：aaa                输出：3   说明/提示 (1 le n le 1.1 times 10^7)      思路分析 思路一（Brute Force）： 由题目意思我们不难想到一个最暴力的做法，我们可以以字符串中的每个字符为中点，比较左右两个字符是否相等，然后逐渐扩大半径，直至求出结果，代码如下。 P3805(bf).cpp Copy to clipboard 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; void solve() { string s; cin >> s; int maxn = 0; int n = s.length(); for (int i = 0; i < n; i++) { int r = 0; // 以 i 为中心的奇数长度回文串 while (i – r >= 0 && i + r < n) { // 对两侧逐一比较，若是不同则跳出循环，相同则 … 阅读更多