首页 > 其他 > 详细

【CodeForces727E/CF727E】Games on a CD (字符串哈希)

时间:2018-07-11 23:50:54      阅读:376      评论:0      收藏:0      [点我收藏+]

题目:

CodeForces727E

分析:

看到字符串比较,肯定想到哈希啊……现学的哈希,先丢两个重要的公式
(\(seed\)是大于字符集大小的质数,\(p\)是大质数)
\[hash[i]=(hash[i-1]*seed+s[i])mod \ p\]
\[hash[l,r]=(hash[r]-hash[l-1]*seed^{r-l+1})mod \ p\]
把哈希想象成\(seed\)进制数,第二个公式很容易推出来。注意写的时候要防止出现负数(详见代码)

为了降低取模后不同字符串获得相同哈希值 ("冲突") 的可能性,这里分别对两个不同的\(p\)取模,即“双哈希”。

既然原字符串是一个“环”,那么自然能想到将其复制一份接在原串末尾,然后枚举起始位置。由于模板串长\(k\)一定,且原串每一位都应该匹配,那么显然当起始位置一定则方案一定,且只需要枚举原串前\(k\)个位置作为起始位置即可讨论到所有情况。

对于每一个起始位置可以\(O(n)\)找出每一个位置的匹配方案,因此最终时间复杂度是\(O(nk)\)

代码:

不能不取模,也不能乱取模;不能偷懒直接把str倍长……否则就会像我一样在CF上惨遭卡常233
技术分享图片

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
using namespace std;

namespace zyt
{
    typedef long long ll;
    typedef pair <ll, ll> pll;
    const int N = 1e6 + 10, seed = 131, p[2] = {(int)1e9 + 7, (int)1e9 + 9};
    ll F[N * 2][2], h[N * 2][2];
    string str;
    map <pll, int> id;
    inline void init(const string &str)
    {
        F[0][0] = F[0][1] = 1;
        for (int i = 1; i < str.size(); i++)
        {
            F[i][0] = F[i - 1][0] * seed % p[0];
            F[i][1] = F[i - 1][1] * seed % p[1];
        }
        h[0][0] = h[0][1] = str[0] - ‘a‘;
        for (int t = 0; t < 2; t++)
            for (int i = 1; i < str.size(); i++)
                h[i][t] = (h[i - 1][t] * seed + str[i] - ‘a‘) % p[t];
    }
    inline pll Hash(const string &s)
    {
        ll ans[2] = {0, 0};
        for (int t = 0; t < 2; t++)
            for (int i = 0; i < s.size(); i++)
                ans[t] = (ans[t] * seed + s[i] - ‘a‘) % p[t];
        return make_pair(ans[0], ans[1]);
    }
    inline pll Hash(const int l, const int r)
    {
        int len = r - l + 1;
        if (l == 0)
            return make_pair(h[r][0], h[r][1]);
        else
            return make_pair(
                (h[r][0] - h[l - 1][0] * F[len][0] % p[0] + p[0]) % p[0], 
                (h[r][1] - h[l - 1][1] * F[len][1] % p[1] + p[1]) % p[1]);
    }
    void work()
    {
        int n, k, g, len;
        static char buf[N];
        string str;
        bool flag = false;
        scanf("%d%d", &n, &k);
        len = n * k;
        scanf("%s", buf);
        str = buf;
        str += str.substr(0, k);
        init(str);
        scanf("%d", &g);
        for (int i = 0; i < g; i++)
        {
            scanf("%s", buf);
            str = buf;
            id[Hash(str)] = i;
        }
        static int ans[N], vis[N];
        memset(vis, -1, sizeof(vis));
        for (int i = 0; i < k && !flag; i++)
        {
            pll p;
            int cnt = 0;
            for (int j = i; j < len + i && cnt < n; j += k)
                if (id.count(p = Hash(j, j + k - 1)) && vis[id[p]] != i)
                    ans[cnt++] = id[p], vis[id[p]] = i;
                else
                    break;
            if (cnt == n)
                flag = true;
        }
        if (flag)
        {
            printf("YES\n");
            for (int i = 0; i < n; i++)
                printf("%d ",  ans[i] + 1);
        }
        else
            printf("NO\n");
    }
}
int main()
{
    zyt::work();
    return 0;
}

【CodeForces727E/CF727E】Games on a CD (字符串哈希)

原文:https://www.cnblogs.com/zyt1253679098/p/9297282.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!