回文字符串总结（回文串判定+最长回文子序列）
回文字符串小结（回文串判定+最长回文子序列）
定义：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
- 回文串判定
例1：hdu2029
题意：请写一个程序判断读入的字符串是否是“回文”。
思路：回文串最基本的判定法是将一个字符串扫一遍，判断第i个字符和倒数第i个字符是否相同，不相同则返回false。
也可以用栈来实现，复杂度均为O(n)。
code：/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
bool Ishuiwen(string s){
int len = s.length();
for(int i = 0 ; i <= len/2 ; i++)
if(s[i] != s[len-i-1]) return false;
return true;
}
int main(){
int T;
cin >> T;
while(T--){
string s;
cin >> s;
if(Ishuiwen(s)) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}
例2：hdu1318
题意：这题是源自uva的一道题，刘汝佳的白书也有推荐，这题大意是判断字符串是否成镜面对称，比如说AOA就是一个镜面对称回文串，BoB就只是普通的回文串，而3AE则是一个镜面对称的非回文字符串（3和E成镜面对称），写程序判断一个字符串是哪种（对称回文，非对称回文，对称非回文，非回文）。
思路：回文字符串判定的进阶，增加了对称字符串的判断，直接模拟即可，对称关系可直接打表。
code：
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
string s0 = "_ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
string s1 = "_A 3 HIL JM O 2TUVWXY51SE Z 8 0";
bool isPalindrome(string str){
for(int i = 0, len = str.length(); i <= len/2; i++)
if(str[i] != str[len-i-1]) return 0;
return 1;
}
bool isMirroed(string str){
for(int i = 0, len = str.length(); i <= len/2; i++){
if((str[i] == '0' && str[len-1-i]=='O') || (str[i] == 'O' && str[len-i-1]=='0')) continue;
else if(s1[s0.find(str[i])] != str[len-i-1]) return 0;
}
return 1;
}
int main(){
string s;
while(cin >> s){
if(isMirroed(s)){
if(isPalindrome(s)) cout << s<< " -- is a mirrored palindrome.";
else cout << s << " -- is a mirrored string.";
}else{
if(isPalindrome(s)) cout << s << " -- is a regular palindrome.";
else cout << s << " -- is not a palindrome.";
}
cout << "\n\n";
}
return 0;
}
- 最长回文子序列
例题：hdu3068
题意：输入不超过1200个长度不超过110000的字符串，输出每一个字符串的最长回文子序列的长度。
思路：如果不考虑时限，这道题我们可以有很多种做法。
由浅到深，最容易想到的就是暴力法，遍历字符串子序列+回文字符串判定，需要O(n^3)的时间复杂度；
其次再想想的话可以想到动态规划（dp大法好！），只要记住一点，回文字符串的子串（这个子串指的是左右边界往里缩相等长度形成的子串）也是回文串，于是我们可以用p[i][j]=1来表示起始位置为s[i]，结束位置为s[j]的字符串是回文串，则若p[i][j] = 1，则p[i+1][j-1]也等于1，即p[i][j] = (p[i+1][j-1]&&s[i]==s[j])? 1:0。dp法时间复杂度可降低到O(n^2)，但空间复杂度需要增加到O(n^2)；
此外还有一种做法是从字符串每一位置开始往外扫描，直到不是回文串为止，时间空间复杂度和dp一致，但需要处理是奇数长度串还是偶数长度串，处理方法是先按奇数串扫描一次，再按偶数串扫描一次；
以上三个做法属于我勉强能想到的，但都不适合这题，RE且TLE。。。
那么还有时间复杂度不超过O(nlogn)，空间复杂度不超过O(nlogn)的方法吗？
有，而且空间时间都只需要O(n)。
这便是Manacher算法。
Manacher's Algorithm
这里有三篇讲manacher算法比较好的博客，感谢这些作者：
http://www.felix021.com/blog/read.php?2040
http://blog.****.net/xingyeyongheng/article/details/9310555
http://www.cnblogs.com/BigBallon/p/3816890.html
准确来说，manacher算法是基于上述第三种做法的拓展，首先通过在字符之间插入‘#’的方式预处理将奇偶字符串都化为奇数串：
以字符串12212321为例
经过上一步，变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]，也就是把该回文串“对折”以后的长度），比如S和P的对应关系：
-------------------------------------------------------------
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
-------------------------------------------------------------
可以看出，P[i]-1正好是原字符串中回文串的总长度。
而后结合代码来看后续处理过程：
void manacher(string s)
{
int id = 0, mx = 0; // <span style="font-family: Tahoma, Arial; line-height: 19.459999084472656px;"><span style="font-size:18px;">id 表示最大回文子串中心的位置，mx = id+P[id]，也就是最大回文子串的边界</span></span>
P[0] = 0; //P[0]不作处理
for(int i = 1 ; i < s.length() ; i++) //扫描串
{
if(mx > i) //如果mx比当前i大，分为两种情况：s[id]为中心的回文串是否包含s[i]为中心的回文串，详细可以看推荐博客中的图示
P[i] = min(P[2*id-i],mx-i); // 2*id-i 表示 i 关于 id 对称的点；前者表示包含，后者表示不包含
else //如果mx比i小，没有可以利用的信息，那么就只能从头开始匹配
P[i] = 1;
while(s[i + P[i]] == s[i - P[i]]) P[i]++; //累计不同回文串之间重复部分
if(mx < P[i] + i) //检测是否需要更新mx以及id
{
mx = P[i] + i;
id = i;
}
}
}
code:
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int p[210005];
char s[210005];
char s1[210005];
void init(char *s){
int j = 2;
s1[0] = '$';
s1[1] = '#';
for(int i = 0 ; s[i] != '\0' ; i++){
s1[j++] = s[i];
s1[j++] = '#';
}
s1[j] = '\0';
}
int manacher(char *s){
int mx = 0 , id = 0;
p[0] = 0;
int l = strlen(s);
for(int i = 1; s[i] != '\0' ; i++){
if(mx > i) p[i] = min(p[2*id - 1] , mx - i);
else p[i] = 1;
while(s[i - p[i]] == s[i + p[i]]) p[i] ++;
if(mx < p[i]+i){
mx = p[i] + i;
id = i;
}
}
// for(int i = 0 ; i < s.length() ; i++) cout << p[i] << ' ';
// cout << "\n";
return *max_element(p,p+l) - 1;
}
int main(){
// freopen("input.txt","r",stdin);
while(scanf("%s",s) != EOF){
init(s);
printf("%d\n",manacher(s1));
}
return 0;
}
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
bool Ishuiwen(string s){
int len = s.length();
for(int i = 0 ; i <= len/2 ; i++)
if(s[i] != s[len-i-1]) return false;
return true;
}
int main(){
int T;
cin >> T;
while(T--){
string s;
cin >> s;
if(Ishuiwen(s)) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
string s0 = "_ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
string s1 = "_A 3 HIL JM O 2TUVWXY51SE Z 8 0";
bool isPalindrome(string str){
for(int i = 0, len = str.length(); i <= len/2; i++)
if(str[i] != str[len-i-1]) return 0;
return 1;
}
bool isMirroed(string str){
for(int i = 0, len = str.length(); i <= len/2; i++){
if((str[i] == '0' && str[len-1-i]=='O') || (str[i] == 'O' && str[len-i-1]=='0')) continue;
else if(s1[s0.find(str[i])] != str[len-i-1]) return 0;
}
return 1;
}
int main(){
string s;
while(cin >> s){
if(isMirroed(s)){
if(isPalindrome(s)) cout << s<< " -- is a mirrored palindrome.";
else cout << s << " -- is a mirrored string.";
}else{
if(isPalindrome(s)) cout << s << " -- is a regular palindrome.";
else cout << s << " -- is not a palindrome.";
}
cout << "\n\n";
}
return 0;
}
经过上一步，变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]，也就是把该回文串“对折”以后的长度），比如S和P的对应关系：
-------------------------------------------------------------
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
-------------------------------------------------------------
可以看出，P[i]-1正好是原字符串中回文串的总长度。
void manacher(string s)
{
int id = 0, mx = 0; // <span style="font-family: Tahoma, Arial; line-height: 19.459999084472656px;"><span style="font-size:18px;">id 表示最大回文子串中心的位置，mx = id+P[id]，也就是最大回文子串的边界</span></span>
P[0] = 0; //P[0]不作处理
for(int i = 1 ; i < s.length() ; i++) //扫描串
{
if(mx > i) //如果mx比当前i大，分为两种情况：s[id]为中心的回文串是否包含s[i]为中心的回文串，详细可以看推荐博客中的图示
P[i] = min(P[2*id-i],mx-i); // 2*id-i 表示 i 关于 id 对称的点；前者表示包含，后者表示不包含
else //如果mx比i小，没有可以利用的信息，那么就只能从头开始匹配
P[i] = 1;
while(s[i + P[i]] == s[i - P[i]]) P[i]++; //累计不同回文串之间重复部分
if(mx < P[i] + i) //检测是否需要更新mx以及id
{
mx = P[i] + i;
id = i;
}
}
}
code:
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int p[210005];
char s[210005];
char s1[210005];
void init(char *s){
int j = 2;
s1[0] = '$';
s1[1] = '#';
for(int i = 0 ; s[i] != '\0' ; i++){
s1[j++] = s[i];
s1[j++] = '#';
}
s1[j] = '\0';
}
int manacher(char *s){
int mx = 0 , id = 0;
p[0] = 0;
int l = strlen(s);
for(int i = 1; s[i] != '\0' ; i++){
if(mx > i) p[i] = min(p[2*id - 1] , mx - i);
else p[i] = 1;
while(s[i - p[i]] == s[i + p[i]]) p[i] ++;
if(mx < p[i]+i){
mx = p[i] + i;
id = i;
}
}
// for(int i = 0 ; i < s.length() ; i++) cout << p[i] << ' ';
// cout << "\n";
return *max_element(p,p+l) - 1;
}
int main(){
// freopen("input.txt","r",stdin);
while(scanf("%s",s) != EOF){
init(s);
printf("%d\n",manacher(s1));
}
return 0;
}