python

3.5 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`HDU\ 1711\ Number\ Sequence`

题目链接 HDU 1711 Number Sequence

一、题目描述

给一段长度为n的整数s_1以及相对较小长度为m的整数s_2，问在s_1中s_2第一个成功匹配的位置在哪？不存在输出-1。

二、前置知识

三、`Rabin` `Karp`模板

/*
Rabin_Karp：虽说用KMP更好，但是RK算法好理解。简单说一下RK算法的原理：首先把模式串的哈希值算出来，
在文本串里不断更新模式串的长度的哈希值，若相等，则找到了，否则整个模式串的长度的哈希值向右移动一位
*/
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int N = 1e4 + 10;
const int M = 1e6 + 10;
const ULL KEY = 100000007;
int s[M], p[N];
int n, m;

int match() {
    ULL h = 1;
    for (int i = 0; i < n; i++) h *= KEY;

    //对齐0~n-1
    ULL ah = 0, bh = 0;
    for (int i = 0; i < n; i++) ah = ah * KEY + s[i]; //模拟成KEY进制，然后利用ULL溢出的形式，相当于对2^64取模
    for (int i = 0; i < n; i++) bh = bh * KEY + p[i];

    //开始尝试匹配
    for (int i = 0; i <= m - n; i++) {
        if (ah == bh) return i + 1; //如果HASH值一致，则返回匹配位置，因本题要求数组下村从1开始，所以+1后返回
        if (i < m - n) ah = ah * KEY + s[i + n] - s[i] * h; //怕越界，因为数据弱，不写if也能AC，但如果模式串最后一位是0，就狒狒了，原因看EXCEL
    }
    return -1;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &m, &n);
        for (int i = 0; i < m; i++) scanf("%d", &s[i]); //源串
        for (int i = 0; i < n; i++) scanf("%d", &p[i]); //模式串
        printf("%d\n", match());
    }
    return 0;
}

四、`Kmp`模板

#include "bits/stdc++.h"
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];

// KMP算法的模板例题. 只不过需要换成int进行操作
int s[M], p[N]; // p串短用n,s串长用m,变量名称不要记忆错误

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &m, &n);
        for (int i = 1; i <= m; i++) scanf("%d", &s[i]); //原串
        for (int i = 1; i <= n; i++) scanf("%d", &p[i]); //模式串

        // 求NE数组
        for (int i = 2, j = 0; i <= n; i++) {
            while (j && p[i] != p[j + 1]) j = ne[j];
            if (p[i] == p[j + 1]) j++;
            ne[i] = j;
        }

        // KMP
        bool flag = false;
        for (int i = 1, j = 0; i <= m; i++) {
            while (j && s[i] != p[j + 1]) j = ne[j];
            if (s[i] == p[j + 1]) j++;
            if (j == n) {
                // 由于题目题目描述的数组下标从1开始，所以追加1
                printf("%d\n", i - n + 1);
                flag = true;
                //防止多次匹配成功：本题要求输出第一个匹配，所以需要及时break,并且注释掉 j=ne[j]
                break;
                // j = ne[j];
            }
        }
        //如果没有匹配成功，则输出-1
        if (!flag) printf("%d\n", -1);
    }
    return 0;
}

3.5 KiB Raw Permalink Blame History Unescape Escape

HDU\ 1711\ Number\ Sequence