TopCoder SRM601: WinterAndReindeers

文字列 A、B から文字列 C を内包する最小限の区間を全て列挙する。

A : [A1] [C を内包する区間] [A2]
B : [B1] [C を内包する区間] [B2]

としたとき、

• [A1][B1]の LCS の長さ + C の長さ + [A2]と[B2]の LCSの長さ

の最大値が答えになる。(LCS: 最長共通部分列)

ただし、それぞれの LCS をいちいち独立に求めると時間が足りないので、ちゃんと計算結果を使いまわすようにする。

public class WinterAndReindeers {
    struct Interval {
        public int From, To;
    }

    IEnumerable<Interval> GetIntervals(string s, string pattern) {
        int n = s.Length;
        int m = pattern.Length;
        var list = new List<Interval>();
        for (int i = 0; i < n; i++) {
            if (s[i] == pattern[0]) {
                int cur = 0;
                for (int j = i; j < n; j++) {
                    if (s[j] == pattern[cur]) {
                        cur++;
                        if (cur >= pattern.Length) {
                            list.Add(new Interval() { From = i, To = j });
                            break;
                        }
                    }
                }
            }
        }
        return list;
    }

    int?[, ,] memo;

    public int LCS(string A, string B, int p1, int p2, bool down = true) {
        if (p1 < 0 || p2 < 0 || p1 >= A.Length || p2 >= B.Length)
            return 0;
        if (!memo[p1, p2, down ? 1 : 0].HasValue) {
            int val = 0;
            int dp = down ? -1 : 1;

            if (A[p1] == B[p2]) {
                val = Math.Max(val, LCS(A, B, p1 + dp, p2 + dp, down) + 1);
            }
            val = Math.Max(val, LCS(A, B, p1 + dp, p2, down));
            val = Math.Max(val, LCS(A, B, p1, p2 + dp, down));
            memo[p1, p2, down ? 1 : 0] = val;
        }
        return memo[p1, p2, down ? 1 : 0].Value;
    }

    public int getNumber(string[] allA, string[] allB, string[] allC) {
        var A = string.Concat(allA);
        var B = string.Concat(allB);
        var C = string.Concat(allC);

        var intervalA = GetIntervals(A, C);
        var intervalB = GetIntervals(B, C);

        int ans = 0;

        memo = new int?[2505, 2505, 2];

        foreach (var iA in intervalA) {
            foreach (var iB in intervalB) {
                int sub =
                    LCS(A, B, iA.From - 1, iB.From - 1, down: true) +
                    LCS(A, B, iA.To + 1, iB.To + 1, down: false) +
                    C.Length;
                ans = Math.Max(ans, sub);
            }
        }

        return ans;
    }
}