题目链接:
基准时间限制:1 秒 空间限制:131072 KB 分值: 0
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str,输出Str里最长回文子串的长度。
Input
输入Str(Str的长度 <= 100000)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5
题解:
普通的方法是枚举中心,然后向两边扩展。时间复杂度为O(n^2),而这里的数据量:len<=1e5,所以会超时。
Manacher算法:O(n)求出最长回文子串。(为什么是线性复杂度?自己也不太清楚,应该是mx为线性增长。)
(注:在首端加‘$’是防止在向左右扩散时在左端溢出(右端已经有‘\0’,故无需再设一个‘$’)。)
代码如下:
1 #include2 using namespace std; 3 typedef long long LL; 4 const double eps = 1e-6; 5 const int INF = 2e9; 6 const LL LNF = 9e18; 7 const int mod = 1e9+7; 8 const int maxn = 1e5+10; 9 10 char s[maxn], Ma[maxn<<1];11 int Mp[maxn<<1];12 13 int Manacher(char *s, int len)14 {15 int ret = 0;16 int l = 0;17 //开头加个特殊符号,以防止下标溢出( while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;)18 //由于结尾有'\0',所以无需再添加19 Ma[l++] = '$'; Ma[l++] = '#';20 for(int i = 0; i =i?min(Mp[2*id-i], mx-i):0; //如果能覆盖到i,则得到以i为中心,最小的回文度;否则从0开始33 while(Ma[i-Mp[i]-1]==Ma[i+Mp[i]+1]) Mp[i]++; //往两边扩展34 if(i+Mp[i]>mx) //更新mx和id35 {36 mx = i+Mp[i];37 id = i;38 }39 ret = max(ret,Mp[i]);40 }41 return ret;42 }43 44 int main()45 {46 cin>>s;47 cout<< Manacher(s, strlen(s)) <