TopCoder SRM607: PalindromicSubstringsDiv2

愚直に全部分文字列が回文であるかどうかを判定すると \(O(N^3)\) になる。

Sのi番目からj番目の範囲の部分文字列を S[i,j] とすると、S[i,j] が回文である条件は、S[i] == S[j] かつ S[i+1,j-1] が回文になることである。これを理由して動的計画法を適用すると \(O(N^2)\) になる。

しかしわざわざ動的計画法を使わなくても、S[i,i] と S[i,i+1] から回文判定しながら左右に範囲を広げていけば、ただのループ処理で書ける。

String.Concat(S1) + String.Concat(S2)とするより String.Concat(S1.Concat(S2)) としたほうがバイト数が下がることに気づいた。

試してないけれど、ローリングハッシュと二部探索を上手く使うと \(O(N \log(N))\) に落とせると思う。

public class PalindromicSubstringsDiv2 {
    public int count(string[] S1, string[] S2) {
        var S = String.Concat(S1.Concat(S2));
        int n = S.Length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k <= 1; k++) {
                int p1 = i;
                int p2 = i + k;
                while (p1 >= 0 && p2 < n && S[p1] == S[p2]) {
                    ans++;
                    p1--;
                    p2++;
                }
            }
        }
        return ans;
    }
}