Manacher算法:O(n)求字符串的最长回文串
1:算法可以在O(n)的时间内求出以每一个字符为中心的最长回文串
2:算法把奇数回文串和偶数回文串统一起来考虑
3:算法大致过程是这样。先在每两个相邻字符中间插入一个分隔符,当然这个分隔符要在原串中没有出现过。一般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了(见下面的一个例子,回文串长度全为奇数了),然后用一个辅助数组rad记录以每个字符为中心的最长回文串的信息。rad[i]记录的是以字符str[i]为中心的最长回文串,当以str[i]为第一个字符,这个最长回文串向右延伸了rad[i]个字符。
原串: w aa bwsw f d
新串: $# w # a # a # b # w # s # w # f # d #\n;
辅助数组P: 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1
4 这里有一个很好的性质,rad[i]-1就是该回文子串在原串中的长度(包括‘#’)。
5 由于这个算法是线性从前往后扫的。那么当我们准备求rad[i]的时候,i以前的rad[j]我们是已经得到了的。我们用mx记在i之前的回文串中,延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。
6 为了防止字符比较的时候越界,字符串第一个位置加了另一个特殊字符‘$’,最后一个还是'\0'不用变,因此新串下标是从1开始的.
7 通过下面这句话,算法避免了很多没必要的重复匹配。
if(mx > i)
rad[i] = min(rad[2*id-i],mx-i);
那么这句话是怎么得来的呢,其实就是利用了回文串的对称性,如下图,
模板:
#define MAXN 240010
int ans;
char tmpStr[MAXN];
char String[MAXN];
int rad[MAXN];
/*求rad数组*/
void manacher(){
ans = 0;
int mx = 0;
int id;
int len = strlen(String);
for(int i = 1 ; i < len ; i++){
if(mx > i)
rad[i] = min(rad[2*id-i] , mx-i);
else
rad[i] = 1;
for(; String[i+rad[i]] == String[i-rad[i]] ; rad[i]++);
if(rad[i]+i > mx){
mx = rad[i]+i;
id = i;
}
ans = max(ans , rad[i]);
}
}
int main(){
while(scanf("%s" , tmpStr) != EOF){
/*求String*/
int pos = 0;
int len = strlen(tmpStr);
String[pos++] = '$';
for(int i = 0 ; i <= len ; i++){/*这里是枚举到len*/
String[pos++] = '#';
String[pos++] = tmpStr[i];
}
manacher();
printf("%d\n" , ans-1);/*输出最长的长度*/
}
return 0;
}
分享到:
相关推荐
Leetcode 1312. 让字符串成为回文串的最少插入次数问题描述1312. 让字符串成为回文串的最少插入次数 - 力扣(LeetCode)算法解法1: 递
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和j 对称,以S[i]为中心的回文子串必然包含
125.验证回文串* [125] 验证回文串解法 1: 双指针。
5.7 字符串算法-后缀树后缀树系列一:概念以及实现原理( the Ukkonen algorithm)后缀树系列二:线性时间内构建后缀树(包含代码实现)后缀树
list some String Hash algorithm, you can use it directly.
479.最大回文数乘积* [479] 最大回文数乘积解法 1: 枚举const MOD = BigInt(1337)
字符串匹配之Sunday算法(英文原版)
字符串匹配算法之Horspool算法(英文原版)
【优化求解】基于磷虾群算法Krill Herd Algorithm求解最优目标matlab源码.zip
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS ...3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能
这是一个关于字符串匹配的kmp算法,程序简单精炼,可以借鉴一下
1.(),[]是括号匹配的字符串 2.若A是括号匹配的串,则(A),[A]是括号匹配的字符串 3.若A,B是括号匹配的字符串,则AB也是括号匹配的字符串
智能优化算法求解车辆路径和车间调度优化问题的C++程序
编写一函数char *my_replace(char *s1, char *s2, char *s3), 实现如下功能:把字符串s1中所有出现的字符串s2都替换成字符串s3,并通过函数名返回替换后的新字符串,但不得破坏s1。例如,当s1=“aabcdabce”, s2=...
本文实例讲述了C语言实现输入一个字符串后打印出该字符串中字符的所有排列的方法,属于数学里的排列问题。是一个很实用的算法技巧。分享给大家供大家参考。具体实现方法如下: 例如输入字符串abc,则输出由字符a、b...
克努斯-莫里斯-普拉特算法,...在一个“主文本字符串” S 内查找一个“词” W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始,以此避免对以前匹配过的字符重新检查。
数据结构_字符串 字符串 堆的动态分配 //堆 动态分配 //realloc函数⽤于修改⼀个原先已经分配的内存块的⼤⼩,可以使⼀块内存的扩⼤或缩⼩。 //void *realloc (void *ptr, size_t new_size ); #include <iostream> #...
字符串转换整数 (atoi) 中等 Algorithm 9 回文数 简单 Algorithm 10 正则表达式匹配 困难 Algorithm 11 盛水最多的容器 中等 Algorithm 12 整数转罗马数字 中等 Algorithm 13 罗马数字转整数 简单 Algorithm 14 最长...
字符串匹配是很多语言中很常用的功能, 比如 js 中就有 indexof(), python 中也有 find()等, 这些底层依赖的就是字符串匹配算法两种最简
链表,数学0003无重复字符的最长子串JavaScript中等哈希表,双指针,字符串0004寻找两个正序数组的中位数JavaScript困难数组,二分查找,分治算法0005最长回文子串中等字符串,动态规划0006Z 字形变换中等字符串0007...