kmp && kmp next的应用

1.kmp模板题：

给定两个数字序列 a[] 和 b[]，b[] 有可能整体作为一个连续子序列出现在了 a[] 中，现在请你找出 b[] 在 a[] 中第一次出现的位置（起始位置从 1 开始计数），如果一次都没有出现，请输出 -1。

输入格式

第一行包含一个数字 T，表示测试用例的个数。
对于每组测试用例，第一行包含两个数字 n m ( 1<= n <= 1000000, 1 <= m <= 10000 )，表示 a[] 和 b[] 的长度。
接下来的一行包括 n 个数字，依次表示 a[1], a[2], a[3] ... a[n]，-1000000 <= a[i] <= 1000000 
接下来的一行包括 m 个数字，依次表示 b[1], b[2], b[3] ... b[m]，-1000000 <= b[i] <= 1000000

输出格式

对于每组数据输出一行，请输出 b[] 整体作为一个连续子序列在 a[] 中的首次出现位置的起始下标，如果一次都没有完整出现，输出 -1。

样例输入

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

样例解释

对于第一组数据，1 2 1 2 3 [1 2 3 1 3] 2 1 2，首次出现位置的起始下标为 6。
对于第二组数据，b[] 没有出现在 a[] 中，输出 -1。

kmp && kmp next的应用

原文：https://www.cnblogs.com/lipu123/p/14590402.html