C++で最短の回文

文字列sがあるとします。その前に文字を追加することで、回文に変換できます。この情報を実行することで見つけることができる最短の回文を見つける必要があります。したがって、文字列が「abcc」のような場合、結果は「ccbabcc」になります。

これを解決するには、次の手順に従います-

• n：=sのサイズ、s1：=s、s2：=s

• 文字列s2を逆にします

• s2：=s concatenate "＃" concatenate s2

• s2と同じサイズの配列lpsを定義します

• j：=0、i：=1

• i

  • s2[i]がs2[j]と同じ場合、

    • lps [i]：=j + 1

    • iを1増やし、jを1増やします

  • それ以外の場合

    • j> 0の場合、j：=lps [j-1]

    • それ以外の場合は、iを1増やします

• extra：=lps [size of s –1]からn--lps [size of lps-1]）

  までのsの部分文字列

• 余分なリバース

• 余分な連結を返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string shortestPalindrome(string s) {
      int n = s.size();
      string s1 = s;
      string s2 = s;
      reverse(s2.begin(), s2.end());
      s2 = s + "#" + s2;
      vector <int> lps(s2.size());
      int j = 0;
      int i = 1;
      while(i <s2.size()){
         if(s2[i] == s2[j]){
            lps[i] = j + 1;
            j++;
            i++;
         } else {
            if(j > 0){
               j = lps[ j - 1];
            } else {
               i++;
            }
         }
      }
      string extra = s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1]);
      reverse(extra.begin(), extra.end());
      return extra + s;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestPalindrome("abcc"));
}

入力

“abcc”

出力

ccbabcc