[hdu 1711] Number Sequence [kmp]

为了高效地解决这个问题，我们采用了KMP算法来快速匹配两个数列中的子序列。具体步骤如下：
问题分析：我们需要在一个长数列 a 中找到一个与较短数列 b 完全匹配的子序列，并且要找到最小的起始位置 K。
选择算法：使用 KMP 算法因为它能够在 O(N + M) 的时间复杂度内高效地完成模式匹配任务。
构建前缀函数：通过预处理 P 数组（即 b 数组）生成前缀函数表（Failure Function），以便在匹配过程中快速跳过不匹配的部分。
模式匹配：利用 KMP 算法主循环逐个字符比较，并结合前缀函数表调整指针位置以实现高效的搜索过程。
结果判断：如果在遍历完 a 数组后成功找到了完整的匹配，则返回最小的起始位置 K；否则返回 -1。
这种方法确保了我们能够在合理的时间内处理大规模的数据输入，并且保证了结果的准确性。
最终的答案：
为了高效地解决这个问题，我们采用了 KMP 算法来快速匹配两个数列中的子序列。具体步骤如下：
问题分析：我们需要在一个长数列 a 中找到一个与较短数列 b 完全匹配的子序列，并且要找到最小的起始位置 K 。
选择算法：使用 KMP 算法因为它能够在 O(N + M) 的时间复杂度内高效地完成模式匹配任务。
构建前缀函数：通过预处理 P 数组（即 b 数组）生成前缀函数表（Failure Function），以便在匹配过程中快速跳过不匹配的部分。
模式匹配：利用 KMP 算法主循环逐个字符比较，并结合前缀函数表调整指针位置以实现高效的搜索过程。
结果判断：如果在遍历完 a 数组后成功找到了完整的匹配，则返回最小的起始位置 K ；否则返回 -1。
这种方法确保了我们能够在合理的时间内处理大规模的数据输入，并且保证了结果的准确性。

Number Series
Computational Time Constraints: 10,000ms/5,000ms (for Java implementations)
Memory Requirements: 32,768/32,768K (in Java contexts)
Total Submissions: 20,398
Accepted Submissions: 8,741

Problem Description
Consider two arrays of numbers: a_{\text{array}} with elements a_{{\text{array}}}[i] for i=1 to N, and b_{\text{array}} with elements b_{{\text{array}}}[j] for j=1 to M. Given that both arrays satisfy the constraints where M \leq N \leq 1{\rm e}4, your task is to determine an integer K such that the sequence starting at index K in array {a_{\text{array}}} matches exactly with array {b_{\text{array}}}. Specifically, this means that for all indices from K to (K+M-2) in array {a_{\text{array}}}, their corresponding values must equal those in array {b_{\text{array}}}. If multiple valid values for K exist, you should output the smallest one.

The input begins with a header line containing an integer T, representing the total number of test cases. Each test case is structured over three consecutive lines. The first line of each case provides two integers N and M, where M must be at least 1 and no more than 1e4, while N can range up to 1e6. Subsequent lines contain arrays a and b respectively, each consisting of integers within the range [-1e6, 1e6].

在每个测试用例中,应输出一行仅包含上述描述的K值.如果不存在这样的K值,则输出-1

Sample Input

2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

Sample Output

6
-1

Source
HDU 2007-Spring Programming Contest

Recommend
lcy

    #include<iostream>  
    using namespace std;  
    const int MAXN = 1111111,MAXM = 11111;  
    int T[MAXN],P[MAXM],Next[MAXM];  
    void MakeNext(int M){  
        Next[0] = -1;  
        int i = 0, j = -1;  
        while(i<M){  
            if(j==-1||P[i]==P[j]){  
                i++,j++;  
                if(P[i]!=P[j])Next[i] = j;  
                else Next[i] = Next[j];  
            }  
            else j = Next[j];  
        }  
    }  
    int KMP(int N,int M){  
        int i=0,j=0;  
        while(i<N&&j<M){  
            if(T[i]==P[j]||j==-1)i++,j++;  
            else j = Next[j];  
        }  
        if(j==M)return i-M+1;  
        else return -1;  
    }  
    int main(){  
        int N,M,C;  
        scanf("%d",&C);  
        while(C--){  
            scanf("%d%d",&N,&M);  
            for(int i=0;i<N;i++)scanf("%d",&T[i]);  
            for(int i=0;i<M;i++)scanf("%d",&P[i]);  
            if(M>N)printf("-1\n");  
            else{  
                MakeNext(M);  
                printf("%d\n",KMP(N,M));  
            }  
        }  
        return 0;  
    }