首页 > 代码库 > Longest Palindromic Substring
Longest Palindromic Substring
求最长回文子串：
回文串是指正着读和反过来读都一样的字符串。
方法：
1. 为了统一解题方法，避免字符串长度奇偶对解题方法的影响，加入了填充字符。若原来的字符串长度为n，则新的字符串长度为2n+1。
2. pos+p[pos] 表示的是目前所有回文子串中，向右达到的最远位置。
3. 先利用对称性，找到p[i]的最小值，然后再进行搜索。
4. 注意数组不要越界！！
class Solution {public: string longestPalindrome(string s) { int pos=0; string sub=s; int maxpos=0; if(!s.size()) return sub; vector<int> p(2*s.size()+1,1); vector<char> str; for(int i=0;i<2*s.size()+1;i++) { if(i%2==0) str.push_back(‘#‘); else str.push_back(s[i/2]); } cout<<"new size:"<<str.size()<<endl; for(int i=1;i<2*s.size();i++) { if(i<p[pos]+pos) { int j=2*pos-i; p[i]=min(p[j],p[pos]+pos-i); } while(i+p[i]<2*s.size()+1&&i-p[i]>=0) { if(str[i+p[i]]==str[i-p[i]]) p[i]++; else break; } if(p[maxpos]<p[i]) maxpos=i; if(p[pos]+pos<p[i]+i) pos=i; } cout<<maxpos<<endl; int begin=(maxpos-p[maxpos]+2)/2; cout<<begin<<endl; for(int i=0;i<2*s.size()+1;i++) cout<<p[i]<<‘ ‘<<endl; sub=s.substr(begin,p[maxpos]-1); return sub; }
Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。