【LeetCode】214.最短回文列結題報告(C++)

原題住所:https://leetcode-cn.com/problems/shortest-palindrome/
タイトルの説明:
文字列sを指定すると、文字列の前に文字を追加することで、文字列をエコー列に変換できます.このように変換できる最短の文列を見つけて返します.
例1:
入力:「aacecaaa」出力:「aaacecaaa」例2:
入力:「abcd」出力:「dcbabcd」
 
問題解決方案:
本題の核心思想はKMPアルゴリズムを採用し、アドレスを参考することである.https://segmentfault.com/a/1190000003797346
大学の本科はKMPのアルゴリズムを学んだことがあって、アルゴリズムは比较的に有名で、ずっとまだあまり理解していません...
文字列の扱い方も巧みで,まず最長の回文列を得てからKMPアルゴリズムを用いて削除する.
コード:

class Solution {
public:
    string shortestPalindrome(string s) {
        //             
        string rev(s);
        reverse(rev.begin(), rev.end());;
        string combine = s + "#" + rev;
        
        //   LPS  
        vector lps(combine.length(), 0);
        int remove = getLPS(combine, lps);
        
        //      ，          
        string prepend = rev.substr(0, rev.length() - remove);
        return prepend + s;
    }
    
    int getLPS(string s, vector& lps){
        // i        ，j        
        int j = 0, i = 1;
        //  j=0，i=1   ，     
        while(i < s.length()){
            //       ，     ，            1
            if(s[i] == s[j]){
                lps[i] = j + 1;
                i ++;
                j ++;
            //     
            } else {
                //             0 ，             
                if(j != 0){
                    j = lps[j - 1];
                //     0 ，             0 
                } else {
                    lps[i] = 0;
                    i ++;
                }
            }
        }
        return lps[lps.size() - 1];
    }
};