leetcode(medium)
5. Longest Palindromic Substring Medium 3635352FavoriteShareGiven a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.Example 2:
Input: "cbbd" Output: "bb"复杂度0（n）
#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int k =1000001;char ma[k] ;int mp[k];string manacher(string s){ string * k=s; int l=0;int len;len=strlen(k); ma[l++]='$'; ma[l++]='#'; for(int i=0;i<len;i++) { ma[l++]=s[i]; ma[l++]='#'; } ma[l]=0; int mx=0,id=0,reslen=0,rescenter=0; for(int i=0;i<l;i++) { mp[i]=mx>i?min(mp[2*id-1],mx-i):1;//利用以知，有动态规划思想 while(ma[i+mp[i]]==ma[i-mp[i]])mp[i]++; if(i+mp[i]>mx) { mx=i+mp[i]; id=i; } if(reslen<mp[i]) { reslen=mp[i]; rescenter=i; } } return s.substr((rescenter-reslen)/2,reslen-1);}int main(){ string s,t; while(cin>>s) { t=manacher(s); cout<<t<<endl;}}
转载于:https://www.cnblogs.com/flyljz/p/10978345.html
