https://leetcode.com/problems/longest-palindromic-substring/
感觉也许O(n)算法可以搞定，于是DP之，各种胡思乱想，于是各种BUG 。。。。。写死了，，然后O(n*n)过掉的，搜下题解，然后发现一个打脸的事情，TM我写过博客
就是这个O(n)算法啊，TMD 真是一朝不做ACM，各种算法全忘光
O(n)算法如下，没的说，裸地暴力
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cstring>;using namespace std;class Solution {public:string longestPalindrome(string s) {int st=0,mx=1;int dp[2005];if(s.size() == 0)return "";dp[0]=1;for(int i=0;i<s.size();i++){if(i+1<s.size()){int cnt=0,flag=0;if(s[i] == s[i+1]){cnt=2;flag=1;for(int j=i-1;j>=0 && j+cnt+1<s.size();j–){if(s[j] == s[j+cnt+1])cnt+=2;else break;}dp[i]=cnt;cnt=1;for(int j=i-1;j>=0 && j+cnt+1<s.size();j–){if(s[j] == s[j+cnt+1])cnt+=2;else break;//cout << i << " " << j << "*" << cnt << endl;}if(cnt > dp[i])dp[i]=cnt;//cout << i << " " << j << "*" << cnt << endl;}else{cnt=1;for(int j=i-1;j>=0 && j+cnt+1<s.size();j–){if(s[j] == s[j+cnt+1])cnt+=2;else break;}dp[i]=cnt;}if(dp[i]>mx){/*if(flag){st = i-dp[i]/2+1;}else{st = i-dp[i]/2;}*/st = i-(dp[i]+1)/2+1;mx = dp[i];}}else{dp[i]=1;}//mx = max(mx, dp[i]);}//cout << st << " " << mx << endl;return s.substr(st,mx);}};int main(){freopen("5in.txt","r",stdin);string s;Solution so;while(cin >> s){cout << so.longestPalindrome(s) << endl;}return 0;}
这一次是一个告别，或者一个永远的告别，
