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。

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