http://codeforces.com/problemset/problem/25/e

直接上solve()函数,简洁明了:

int solve()
{
    int i, j, minlen = mx * 3;
    For(i, 2) Forr(j, i + 1, 3) if (contain(i, j) || contain(j, i))
    {
        int x = len[i] > len[j] ? i : j, y = 3 - i - j;
        if (contain(x, y) || contain(y, x)) return max(len[x], len[y]);
        return len[x] + len[y] - max(overlap(x, y), overlap(y, x));
    }
    do minlen = min(minlen, len[0] + len[1] + len[2] - overlap(id[0], id[1]) - overlap(id[1], id[2]));
    while (next_permutation(id, id + 3));
    return minlen;
}

完整代码:

/*62ms,3400KB*/

const int mx = 100005;
const ull B = 100000007ULL; /// 哈希基数,1e8 + 7,选其他的数(比如123)也能AC

char s[3][mx];
ull ha[3][mx], bp[mx] = {1ULL};
int id[3] = {0, 1, 2}, len[3];

void init_hash()
{
    int i, j;
    For(i, 3) Forr(j, 1, len[i] + 1) ha[i][j] = ha[i][j - 1] * B + s[i][j];
    int n = max(max(len[0], len[1]), len[2]);
    Forr(i, 1, n + 1) bp[i] = bp[i - 1] * B;
}

inline ull get_hash(ull *Ha, int pos, int l) /// 返回Ha[pos...pos+l-1]的值
{
    return Ha[pos + l - 1] - Ha[pos - 1] * bp[l];
}

bool contain(int ida, int idb) /// b是否为a的子串
{
    if (len[ida] < len[idb]) return false;
    ull hab = ha[idb][len[idb]];
    for (int i = 1; i + len[idb] <= len[ida]; ++i)
        if (get_hash(ha[ida], i, len[idb]) == hab) return true;
    return false;
}

int overlap(int ida, int idb)
{
    int ans = 0, i;
    Forr(i, 1, min(len[ida], len[idb]) + 1)
    if (get_hash(ha[ida], len[ida] - i + 1, i) == get_hash(ha[idb], 1, i)) ans = i;
    return ans;
}

int solve()
{
    int i, j, minlen = mx * 3;
    For(i, 2) Forr(j, i + 1, 3) if (contain(i, j) || contain(j, i))
    {
        int x = len[i] > len[j] ? i : j, y = 3 - i - j;
        if (contain(x, y) || contain(y, x)) return max(len[x], len[y]);
        return len[x] + len[y] - max(overlap(x, y), overlap(y, x));
    }
    do minlen = min(minlen, len[0] + len[1] + len[2] - overlap(id[0], id[1]) - overlap(id[1], id[2]));
    while (next_permutation(id, id + 3));
    return minlen;
}

int main()
{
    int i;
    For(i, 3) gets(s[i] + 1), len[i] = strlen(s[i] + 1);
    init_hash();
    PI(solve());
    return 0;
}

Comments

comments powered by Disqus