一般算法 ( 時間複雜度O(N2) )
#include<iostream>
#include<string>
using namespace std;
int main()
{
string a;
cin >> a;
int max = ;
int i, j;
int c;
int size = a.size();
for (i = ; i<size; ++i)//從第一個字元開始判斷
{
for (j = ; i - j >= && i + j < size; ++j)//奇數回文
{
if (a[i - j] != a[i + j])
break;
c = * j + ;
}
if (max < c)
max = c;
for (j = ; i - j >= && i + j + < size; ++j)//偶數回文
{
if (a[i - j] != a[i + j + ])
break;
c = * j + ;
}
if (max < c)
max = c;
}
cout << max << endl;
`
system("pause");
return 0;
}
Manacher算法( 時間複雜度O(N) )
問題描述:
輸入一個字元串,求出其中最大的回文子串。子串的含義是:在原串中連續出現的字元串片段。回文的含義是:正着看和倒着看相同,如abba和yyxyy。
解析:
這裡介紹O(n)回文子串(Manacher)算法
算法基本要點:首先用一個非常巧妙的方式,将所有可能的奇數/偶數長度的回文子串都轉換成了奇數長度:在每個字元的兩邊都插入一個特殊的符号。比如 abba 變成 #a#b#b#a#, aba變成 #a#b#a#。 為了進一步減少編碼的複雜度,可以在字元串的開始加入另一個特殊字元,這樣就不用特殊處理越界問題,比如$#a#b#a#。
下面以字元串12212321為例,經過上一步,變成了 S[] = “$#1#2#2#1#2#3#2#1#”;
然後用一個數組 P[i] 來記錄以字元S[i]為中心的最長回文子串向左/右擴張的長度(包括S[i]),比如S和P的對應關系:
S # # # # # # # # #
P
(p.s. 可以看出,P[i]-正好是原字元串中回文串的總長度)
下面計算P[i],該算法增加兩個輔助變量id和mx,其中id表示最大回文子串中心的位置,mx則為id+P[id],也就是最大回文子串的邊界。
這個算法的關鍵點就在這裡了:如果mx > i,那麼P[i] >= MIN(P[2 * id - i], mx - i)。
具體代碼如下:
if(mx > i)
{
p[i] = (p[*id - i] < (mx - i) ? p[*id - i] : (mx - i));
}
else
{
p[i] = ;
}
當 mx - i > P[j] 的時候,以S[j]為中心的回文子串包含在以S[id]為中心的回文子串中,由于 i 和 j 對稱,以S[i]為中心的回文子串必然包含在以S[id]為中心的回文子串中,是以必有 P[i] = P[j],見下圖。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5yM0gjMwQTNxQDMwEjMxAjMvwFMyYjNyQzLcJTMwIzLcNXZnFWbp9CXt92YuM3ZvxmYuNmLyADMjlGcvw1LcpDc0RHaiojIsJye.png)
當 P[j] > mx - i 的時候,以S[j]為中心的回文子串不完全包含于以S[id]為中心的回文子串中,但是基于對稱性可知,下圖中兩個綠框所包圍的部分是相同的,也就是說以S[i]為中心的回文子串,其向右至少會擴張到mx的位置,也就是說 P[i] >= mx - i。至于mx之後的部分是否對稱,就隻能一個一個比對了。
對于 mx <= i 的情況,無法對 P[i]做更多的假設,隻能P[i] = 1,然後再去比對了
下面給出原文,進一步解釋算法為線性的原因
代碼如下
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s,s1;
cin >> s;
s1 += "$#";
int size = s.size();
for (int i = ; i < size; ++i)
{
s1 += s[i];
s1 += '#';
}
size = s1.size();
int * p = new int[size];
int mx = , id = ;
for (int i = ; i < size; ++i)
{
if (mx > i)
{
p[i] = (p[ * id - i] < (mx - i) ? p[ * id - i] : (mx - i));
}
else
{
p[i] = ;
}
while (s1[i - p[i]] == s1[i + p[i]] && (i + p[i] < size) && ( i - p[i] >= ))
p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
int max = ;
for (int i = ; i < size; i++)
{
if (p[i] > max)
{
max = p[i];
}
}
max--;
cout << max << endl;
delete p;
system("pause");
return ;
}