问题 B: Number Sequence

问题 B: Number Sequence

时间限制: 1 Sec  内存限制: 128 MB
提交: 83  解决: 42
[提交][状态][讨论版][命题人:外部导入]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1717&pid=1

题目描述

Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

输入

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].

输出

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

样例输入

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

样例输出

6

-1

提示

思路：kmp算法模板一套就完事

代码：

#include <bits/stdc++.h>

using namespace std;

int Next[1000000];

void get_next(char *child)

{

    memset(Next, 0, sizeof(Next));

    int i, j;

    j = -1;

    Next[0] = -1;

    i = 0;

    while (i < strlen(child))

    {

         if (j == -1 || child[i] == child[j])// k=-1用于指针i的移动 结合k=next[k]看

         {

             i++;

             j++;

             Next[i] = j;

         }

         else j = Next[j];

    }

}

int kmp(char *parent, char *child)//匹配ab两串，a为父串

{

    int i = 0, j = 0;

    int len1 = strlen(parent);

    int len2 = strlen(child);

    get_next(child);

    while (i < len1&&j < len2)

    {

         if (j == -1 || parent[i] == child[j])

             ++i, ++j;

         else

             j = Next[j];

    }

    if (j == len2)

         return  i - j + 1;

    else

         return -1;

}

char a[1000000], b[1000000];

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

         memset(a, 0, sizeof(a));

         memset(b, 0, sizeof(b));

         int m, n;

         cin >> m >> n;

         for (int i = 0; i < m; i++)cin >> a[i];

         for (int i = 0; i < n; i++)cin >> b[i];

         cout << kmp(a, b) << endl;

    }

    return 0;

}