Cow and Message

codeforces.com

問題

ある文字列Sが与えられる。Sに含まれる部分文字列のうち出現頻度が最も高いものの長さを求めよ

例

• 入力: ababab
• 出力: 6

これにはabが6個入っているので出力は6となっている。

解説

参考: 题解 Codeforces Round #621 (Div. 1 + Div. 2) (CF1307) - kylin_xy - 博客园

こちらの中国の方が書かれた解説を読んで通した。DPに苦手意識がまだある…

上の記事ではなぜ通るのかがあまり解説されていなかったので、なぜ通るか以下に書き下しておく。

DPで解く

この問題はxyあるいはxが最も出現頻度が高くなる(x、yはそれぞれ任意の文字でx != y)。たとえばabcacbacならacが最も出現頻度が高い。

まず、同じ文字が2回以上現れない理由は簡単であろう。なぜならxxyにはxyが2回含まれているため、xxyよりxyのほうが出現頻度が高くなる。

そして、xyzを考えなくて良いかも同様にわかる。xyzにはxyが含まれるのだから、仮にxyzが最も出現頻度が高いとしたら、xyも同じ頻度で現れている。今回の問題は出現頻度さえわかれば良いので、xyだけ着目すればよい。

以上がわかればあとはDPを書くだけとなる。

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using vi = vector<ll>;
template<class T>using vv = vector<vector<T>>;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)

int main() {
  string in(S);
  int N = S.size();

  vv<ll> dp(26, vi(26, 0)); // dp[a][b] = abの出現頻度
  vi count(26, 0);
  rep(i, N) {
    rep(j, 26)
      dp[j][S[i]-'a'] += count[j]; // ここまでにjが出た回数ぶん更にふえる
    ++count[S[i]-'a'];
  }
  ll ans = 0;
  rep(i, 26) rep(j, 26)
    ans =max(ans, max(dp[i][j], count[i]));

  cout << ans << endl;

  return 0;
}