prefix palindrome （バグ有り）

追記：bugあり

• 修正版 https://perogram.hateblo.jp/entry/2020/07/31/100412
• bug発覚となった提出 https://codeforces.com/contest/1326/submission/88547150
  • dvbtpodcvdhhtvltwwrxcでdvを返す...

prefix palindromeの例

aaaabbbbbcc

=> aaaa
(回文としてはbbbbbの方が長いが、prefixではない)

editorial ???

• 文字列のprefixのうち、最大の回文を求めたい
• この問題で必要だった https://codeforces.com/contest/1326/problem/D2
• editorialを見てもよく分からず、tester codeを見てもよく分からなかった。コードはこれ
  • https://pastebin.com/St9RUYvN

const int M = (int)(2e6 + 239);
int pref[M], c;
string solve_palindrome(const string& s)
{
    string a = s;
    reverse(a.begin(), a.end());
    a = s + "#" + a;
    c = 0;
    for (int i = 1; i < (int)a.size(); i++)
    {
        while (c != 0 && a[c] != a[i])
            c = pref[c - 1];
        if (a[c] == a[i])
            c++;
        pref[i] = c;
    }
    return s.substr(0, c);
}

• prefとはprefix functionと書いてあり、一致しなかったらcを減らしていくと理解した
• manacharでやってもいいのかもしれないが、偶数長回文の時はダミー文字を入れる必要がある
  • 例：abba => a#b#b#a としてからmanachar

MP, KMP

• snukeさんのblog記事を読むと、上記コードはMP, KMP法に近い？
• ということで入力sに対してt = s + "#" + rev(s)を作ってKMPしてみたら、同様のprefix palindromeが得られた

string KMP(string s){
  s = s + "#" + rev(s);
  ll L = s.size();
  VI A(2*L, -1);
  int j = -1;
  for (int i = 0; i < L; i++) {
    while (j >= 0 && s[i] != s[j]) j = A[j];
    j++;
    A[i+1] = j;
  }
  ll ma = *max_element(ALL(A));
  return s.substr(0, ma);
}

動作確認コード

string rev(string s){
  reverse(ALL(s));
  return s;
}

// 自作
string KMP(string s){
  s = s + "#" + rev(s);
  ll L = s.size();
  VI A(2*L, -1);
  int j = -1;
  for (int i = 0; i < L; i++) {
    while (j >= 0 && s[i] != s[j]) j = A[j];
    j++;
    A[i+1] = j;
  }
  ll ma = *max_element(ALL(A));
  return s.substr(0, ma);
}

const int M = (int)(2e6 + 239);
int pref[M]; // prefix function
int c;
 
// editorial
string solve_palindrome(const string& s)
{
    string a = s;
    reverse(a.begin(), a.end());
    a = s + "#" + a;
    c = 0;
    for (int i = 1; i < (int)a.size(); i++)
    {
        while (c != 0 && a[c] != a[i])
            c = pref[c - 1];
        if (a[c] == a[i])
            c++;
        pref[i] = c;
    }
    return s.substr(0, c);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    vector<string> S;
    S.push_back("abcbae");
    S.push_back("abae");
    S.push_back("aaaaaa8888888888888888888888bbbbb");

    for(string s : S){
      auto a = KMP(s);
      auto b = solve_palindrome(s);
      debug(s,a,b);
      if(a==b){
        p("same");
      }else{
        p("not same");
      }  
    }
    return 0;
}

editorialの手法とKMPの手法の出力結果が一致することを確認

[s,a,b]: "abcbae" "abcba" "abcba"
same
[s,a,b]: "abae" "aba" "aba"
same
[s,a,b]: "aaaaaa8888888888888888888888bbbbb" "aaaaaa" "aaaaaa"
same

その他

• 最近codeforcesのmanacharについてツイートしている人が多かったので、TLの人はmanacharを使った人が多そう
• 他にもeditorialの方法や、KMPの方法もる
• しかし使い方は分かったものの、内部理解はしていない。それはまだ早い

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)