首页 > 其他 > 详细

HDU-1711-Number Sequence(模式串匹配)

时间:2019-01-23 16:27:05      阅读:157      评论:0      收藏:0      [点我收藏+]
  • Rabin-Karp
    Accepted 1711 904MS 5272K 1310 B G++
    #include "bits/stdc++.h"
    using namespace std;
    typedef long long LL;
    const int MAXN = 1e6 + 5; 
    const int SEED = 1e9 + 7;
    int arr[MAXN];
    int main() {
        int t, n, m, k;
        scanf("%d", &t);
        while (t--) { 
            LL p = 0, s = 0, head = 1;
            bool flag = false;
            scanf("%d%d", &n, &m);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &arr[i]);
            }
            // 获取模式串(M数组)的哈希值 
            for (int i = 1; i <= m; i++) {
                scanf("%d", &k); 
                head *= SEED;
                p = p * SEED + k;
            }
            // 获取arr[0]所表示的长度为m的串的哈希值 
            for (int i = 1; i < m; i++) {
                /*
                比较标准的写法是s = (s * SEED + arr[i]) % MOD;(MOD是一个和SEED互质的数)
                这里利用LL的溢出来省略MOD,可以将MOD看成2的64次方 
                */
                s = s * SEED + arr[i];
            } 
            for (int i = 1; i <= n - m + 1; i++) {
                // 用arr[i - 1]所表示的长度为m的串的哈希值得到arr[i]所表示的长度为m的串的哈希值  
                s = s * SEED - head * arr[i - 1] + arr[i + m - 1];
                if (s == p) {
                    flag = true;
                    printf("%d\n", i);
                    break;
                }
            }
            if (!flag) {
                puts("-1");
            }
        }
        return 0;
    } 

    Rabin-Karp获取哈希值的形式有点像进制转换,由于计算机内二进制加减是不管符号的所以p和s变成负数也无所谓,用unsigned long long和long long是一样的。但是Rabin-Karp不保证匹配结果绝对正确,因为不同的串哈希值可能一样(long long的范围只有2的64次方,但是本题数组值的范围是[-1000000, 1000000],只要三四位产生的串的数量long long就不够放了)所以如果竞赛中用此法错了,可以尝试改SEED。还不行那就只能换方法了。

HDU-1711-Number Sequence(模式串匹配)

原文:https://www.cnblogs.com/Angel-Demon/p/10309508.html

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