perogram

prefix palindrome

prefix palindromeの例

aaaabbbbbcc

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

editorial ???

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);
}

f:id:peroon:20200407202319j:plain

動作確認コード

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の方法もる
  • しかし使い方は分かったものの、内部理解はしていない。それはまだ早い