問題

http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/D.pdf

2つの文字列 $S, T$ がある。一つの部分文字列のアナグラムが、他方の部分文字列に一致するような文字列の最長の長さを求めよ。

$1 \le |S| \le 4000$
$1 \le |T| \le 4000$

解法

アナグラムを考えれば良いので、部分文字列について文字の順序は関係ないことになる。よって累積和を取り、区間について $O(1)$ で含まれている種類ごとの文字数を特定する方法が思いつく。一方の部分文字列を文字数カウントを、 $N \times N$ 個あるそれぞれの区間についてサイズ26の配列として持ち、二分探索木につめる解法が考えられる。そうすることで、区間から平衡二分探索木につめるのに $O(N \times Nlog(N\times N) \times \alpha)$ ( $\alpha$ は文字の種類数) になると考えられる。

しかしこれではなかなか重い上にMLEする。また、ローリングハッシュの要領でサイズ26の配列を1つの64bit整数にまとめる方法も考えられる。空間計算量から文字の種類数 $\alpha$ を消すことができるが、これでもまだMLEは避けられない。平衡二分探索木(set)をハッシュテーブル(unordered_set)にしても、実行速度とメモリの面で多少の改善しか見られない。

区間の全てを平衡二分探索木につめるのをやめて、長さごとに分割して詰める方針を取る。 $O(N)$ の長さに対して、全ての始点をとった部分文字列を平衡二分探索木に詰めたら、その時点でアナグラムの一致判定をする。こうすることで計算量を増やさずにMLEを回避することができ、当日のオープンコンテストの環境でもACすることができる。

array<int, 26> sum[2][4010];
 
typedef unsigned long long ull;
 
const ull B = 1^9+7;
 
int main() {
 
  string S[2];
  int N[2];
 
  rep(i, 2) {
    cin >> S[i];
    N[i] = S[i].size();
  }
 
  rep(k, 2) rep(i, N[k]) {
    rep(j, 26) sum[k][i + 1][j] += sum[k][i][j];
    sum[k][i + 1][S[k][i]-'a']++;
  }
 
  int ans = 0;
 
  REP(length, 1, min(N[1], N[0]) + 1) {
    unordered_set<ull> st;
    rep(i, N[1] - length + 1) {
      auto subsum = sum[1][i + length];
      rep(k, 26) subsum[k] -= sum[1][i][k];
      ull hash = 0;
      rep(k, 26) hash = hash * B + subsum[k];
      st.insert(hash);
    }
 
    rep(i, N[0]) {
      auto subsum = sum[0][i + length];
      rep(k, 26) subsum[k] -= sum[0][i][k];
      ull hash = 0;
      rep(k, 26) hash = hash * B + subsum[k];
      if(st.count(hash)) {
        ans = max(ans, length);
      }
    }
  }
 
  cout << ans << endl;
 
  return 0;
}

感想

オープンコンテスト本番はMLEを回避する方法が思いつかず解くことができなかった。

Logfiles

ICPCOOC2016 D: Hidden Anagrams

問題

解法

感想