数据结构实验之串三：KMP应用 (PS：这题巨坑  呜呜呜。。)

Time Limit: 1000 ms Memory Limit: 65536 KiB

 

Problem Description

有n个小朋友，每个小朋友手里有一些糖块，现在这些小朋友排成一排，编号是由1到n。现在给出m个数，能不能唯一的确定一对值l和r(l <= r)，使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数？

Input

首先输入一个整数n，代表有n个小朋友。下一行输入n个数，分别代表每个小朋友手里糖的数量。

之后再输入一个整数m，代表下面有m个数。下一行输入这m个数。

Output

 如果能唯一的确定一对l,r的值，那么输出这两个值，否则输出-1

Sample Input

5

1 2 3 4 5

3

2 3 4

Sample Output

2 4

Hint

Source

windream

思路：

这道题考察的也是kmp算法，不过，需要注意的是：求得是唯一的一对l和r，需要再加一个判断，看是否是唯一存在的即可。

也有一些坑点  比如222666 和22的情况  这也就注定你的第二次匹配的位置问题

 

#include 
    
     using namespace std;int a[10000001], b[10000001];int nextt[1000001];void get_next(int b[], int n){    nextt[0] = -1;    int j = -1, i = 0;    while (i < n) // i < n-1 也可以    {        if (j == -1 || b[i] == b[j])        {            i++;            j++;            nextt[i] = j;        }        else            j = nextt[j]; // 失配回溯    }}int kmp(int a[], int b[], int m, int n){    int i = 0, j = 0;    // cout<
     
      <
      
       = n)        return i + 1 - n;    // 或return i + 1 - n;  都一样    else        return -1;}int main(){    int m, n;    scanf("%d", &m);    for (int i = 0; i < m; i++)        scanf("%d", &a[i]);    scanf("%d", &n);    for (int i = 0; i < n; i++)        scanf("%d", &b[i]);    get_next(b, n);    int ans1 = kmp(a, b, m, n);    if (ans1 == -1)        printf("-1\n");    else    {        int ans2 = kmp(a + ans1, b, m, n);        // 这个地方必须是  a + ans1  考虑22266 和 22 这种情况  两种匹配的情况有共同元素        if (ans2 == -1)            printf("%d %d\n", ans1, ans1 + n - 1);        else            printf("-1\n");    }    return 0;}