放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

Codeforces 25E Test 题解《挑战程序设计竞赛》

目录

挑战程序设计竞赛第二版.jpg

Codeforces 25E Test 

出题:众所周知,程序竞赛测试数据越变态越好玩。已知3个字符串会使选手的程序出错,出题者想构造一个超级变态数据同时包含这3个字符串。求该母串最小长度。

4.7华丽地处理字符串 

字符串匹配 

利用滚动哈希法可以快速预处理出字符串的哈希值以及基数的n次方表。

hankcs.com 2017-02-05 下午9.29.52.png

如果这些字符串有包含关系,则只取母串x,与剩下的第3个串y进行讨论。如果x和y有包含关系,则取母串作为答案。否则答案为x与y的两种拼接xy和yx中的较小者。

如果没有任何包含关系,那么遍历三个字符串的所有拼接方式,取其最小者作为最终答案。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using ull = unsigned long long;
const int MAX_LENGTH = 100000 + 8;
const ull B = 100000007ULL; // 哈希的基数

char s[3][MAX_LENGTH];
ull H[3][MAX_LENGTH],               // H[i][j] := s_i的长度为j的前缀的哈希值
        B_to[MAX_LENGTH] = {1ULL};  // B_to[i] := B^i
int id[3] = {0, 1, 2}, len[3];

void init_hash()
{
    for (int i = 0; i < 3; ++i)
    {// 初始化前缀的哈希值
        for (int j = 1; j < len[i] + 1; ++j)
        {
            H[i][j] = H[i][j - 1] * B + s[i][j];
        }
    }

    int n = max(max(len[0], len[1]), len[2]);
    for (int i = 1; i < n + 1; ++i)
    {
        B_to[i] = B_to[i - 1] * B;
    }
}

// s[b...b+l)的哈希值
inline ull hash_of(ull *h, int b, int l)
{
    return h[b + l - 1] - h[b - 1] * B_to[l];
}

// b是否在a中出现(a是否包含b)
bool contain(int a, int b)
{
    if (len[a] < len[b])
        return false;
    ull bh = H[b][len[b]]; // b全长对应的哈希值
    for (int i = 1; i + len[b] <= len[a]; ++i) // 对a不断右移一位,更新哈希值并判断
        if (hash_of(H[a], i, len[b]) == bh)    // a从位置i开始长度为len[b]的子串等于b
            return true;
    return false;
}

// a的后缀和b的前缀相等的最大长度
int overlap(int a, int b)
{
    int ans = 0;
    for (int i = 1; i <= min(len[a], len[b]); ++i)
    {// a的长度为i的后缀与b的长度为i的前缀的哈希值是否相等
        if (hash_of(H[a], len[a] - i + 1, i) == hash_of(H[b], 1, i))
            ans = i;
    }

    return ans;
}

int solve()
{
    int ans = MAX_LENGTH * 3;
    for (int i = 0; i < 2; ++i)
    {
        for (int j = i + 1; j < 3; ++j)
        {
            if (contain(i, j) || contain(j, i))
            {
                int x = len[i] > len[j] ? i : j, y = 3 - i - j; // x为母串,y为除母子串外的第三个串
                if (contain(x, y) || contain(y, x))             // x和y有包含关系
                    return max(len[x], len[y]);
                return len[x] + len[y] - max(overlap(x, y), overlap(y, x)); // x和y拼接起来
            }
        }
    }
    do  // 无包含关系,只好遍历所有拼接方式
        ans = min(ans, len[0] + len[1] + len[2] - overlap(id[0], id[1]) - overlap(id[1], id[2]));
    while (next_permutation(id, id + 3));
    return ans;
}

int main()
{
    for (int i = 0; i < 3; ++i)
    {
        gets(s[i] + 1), len[i] = strlen(s[i] + 1);  // 首部预留一个\0,方便递推hash
    }
    init_hash();
    printf("%d\n", solve());
    return 0;
}

hankcs.com 2017-02-05 下午9.27.52.png

Reference

这份模板比书上的要好:http://endless.logdown.com/posts/2014/04/15/codeforces-beta-round-25-25e-test-hash

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » Codeforces 25E Test 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机