C++ 最長迴文子字串 LPS

子字串:字串 bc 為字串 abcd 的子字串。
迴文:a、aa、abcba。
題目:輸出最長迴文子字串的長度、起始index、結尾index。

輸入:wohellollehrld
輸出:
9
3 11

解法

從 s[0] 到 s[n-1],假設 s[i] 為迴文子字串的中心(一個字元或一個空隙),向外擴張。

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> s;
    int maxlen=0, l, r;
    for(int i=0; i<s.length(); i++){
        //odd length
        int x = 0;
        while((s[i-x]==s[i+x]) && (i-x>=0) && (i+x<s.length())){
            x++;
        }
        x--;
        if(2*x+1 > maxlen){
            maxlen = 2*x+1;
            l = i-x;
            r = i+x;
        }
        //even length
        x = 0;
        while( (s[i-x]==s[i+1+x]) && (i-x>=0) && (i+1+x<s.length()) ){
            x++;
        }
        if(2*x > maxlen){
            maxlen = 2*x;
            l = i-x+1;
            r = i+x;
        }
    }
    cout << maxlen << '\n';
    cout << l+1 << ' ' << r+1 << '\n';
}

分享文章!
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。