SRM 488 div1 med: TheBoringStoreDivOne

SRM 488, やたらと boring が出てくるけど競プロer が「頭悪い」って言うのと似た空気を感じる。

問題

TopCoder Statistics - Problem Statement

解法

以前に似たような問題を解いています。
mayokoex.hatenablog.com

B の 2 つの連続部分文字列 C, D では, C の後半と D の後半部分は一致しなければなりません。
例えば, C = "abcdd", D = "cdd" とかだと, "cdd" が一致しているので OK ですが, C = "abaa", D = "ab" とかだと, 最後の 2 文字が "aa" と "ab" で異なるので, どう頑張っても 問題文の A+C と B+D を一致させることは出来ません。

C = "abcdd", D = "cdd" のように後半が一致している場合は, "ab" という差を A, B で作って, A+C, B+D を作れば A+C == B+D となり happy です。
ということで, map に C と D の差である "ab", とその差によって出来る最長共通部分文字列 "cdd" をペアにして保存しておきます。
J について調べるときは, 各連続部分文字列 A, B に対して, A と B の後半の差(例えば A = "abcbb", B = "abc" だったら 差は "bb") を見て, もしその差に対応する C と D の差があればそれが店の名前の候補になります。

その中で一番長い文字列を探せば OK です。

微妙に計算量が怪しい(O(n^5 log n) くらい？) と思いましたが 100ms かかってなかったです。

class TheBoringStoreDivOne {
public:
    string find(string J, string B) {
        map<string, string> mp;
        int jn = J.size(), bn = B.size();
        for (int l1 = 0; l1 < bn; l1++) for (int r1 = l1+1; r1 <= bn; r1++) {
            for (int l2 = r1; l2 < bn; l2++) for (int r2 = l2+1; r2 <= bn; r2++) {
                int len = min(r2-l2, r1-l1);
                if (B.substr(r2-len, len) != B.substr(r1-len, len)) continue;
                string s;
                if (r2-l2 > r1-l1) s = B.substr(l2, r2-l2-len);
                else s = B.substr(l1, r1-l1-len);
                auto it = mp.find(s);
                if (it == mp.end()) mp.insert(make_pair(s, B.substr(r2-len, len)));
                else {
                    int size = it->second.size();
                    if (size < len || ((size == len) && (it->second) > B.substr(r1-len, len)) ) {
                        it->second = B.substr(r1-len, len);
                    }
                }
            }
        }
        string ret;
        for (int l1 = 0; l1 < jn; l1++) for (int r1 = l1+1; r1 <= jn; r1++) {
            for (int l2 = r1; l2 < jn; l2++) for (int r2 = l2+1; r2 <= jn; r2++) {
                int len = min(r2-l2, r1-l1);
                if (J.substr(l1, len) != J.substr(l2, len)) continue;
                string s;
                if (r2-l2 > r1-l1) s = J.substr(l2+len, r2-l2-len);
                else s = J.substr(l1+len, r1-l1-len);
                if (mp.find(s) == mp.end()) continue;
                else s = J.substr(l1, len)+s+mp[s];
                if (ret.size() < s.size() || (ret.size() == s.size() && ret > s)) ret = s;
            }
        }
        return ret;
    }
};