Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13207 Accepted Submission(s): 5979
Problem Description
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.
Input
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].
Output
For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
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 | We have carefully selected several similar problems for you: 3336 3746 1251 2222 1867
题意：找到母串ns[]中子串ms[]第一次出现时，首位的位置
思路：kmp
注意：
1.getnext（）带入的一定是子串ms[]
2.题目为数组，与字符串不同，注意定义类型
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; int t,n,m; int ns[1000005]; int ms[10005]; int nexts[1000005]; void getnext() { int i=0; int k=-1; nexts[0]=-1; while(i<m) { if(k==-1||ms[i]==ms[k]) { i++; k++; nexts[i]=k; } else k=nexts[k]; } } void get_ex() { int j=0,ans=-1; int k=0; getnext(); // printf("%d ",m); while(k<n) { if(j==-1||ns[k]==ms[j]) { j++; k++; } else j=nexts[j]; if(j==m) { // printf("%d ",k); ans=k; break; } } // printf("%d ",m); if(ans!=-1) printf("%d ",ans-m+1); else printf("-1 "); } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) scanf("%d",&ns[i]); for(int j=0; j<m; j++) scanf("%d",&ms[j]); get_ex(); } return 0; }
下面是next数组的预处理核心代码：
void find_next_() {
int j=0,i=1;
next_[1]=0;
while(i<m) {
if(j==0||b[j]==b[i]) {
++i,++j;
if(b[i]!=b[j])next_[i]=j;
else next_[i]=next_[j];
}
else j = next_[j];
}
}
这回是以下图为例来进行示范：（因为上面的例子不太好用）
我们使用KMP预处理对B数组进行一个搜索，然后得到一个next数组，实际上就是统计出B中相同的连续元素，然后进行一个标记的操作
然后我们经过处理后得到的next数组为：
我们先不要管这个数组为什么要通过计算，以及这个数组的作用是什么，我们再来模拟一遍KMP的操作,因为时间原因，我就简单操作一遍，我们直接跳到不同的那个步骤：
经过我们观察，是不是能够发现B[6]之前有着相同的元素1,2,1，那么我们是不是能够让相同的部分重叠，来减少这个匹配所移动的次数呢？
你看这样是不是能一步达到我们所需要的条件，然后我们继续操作，
你看，我们我们又节省了一部分时间，但是没有1 2 1可以匹配了怎么办？没关系，接着往下看，
这样我们又将两个1匹配在了一起，但是A[i]!=B[j]，并且之前只有一个元素可以匹配，完全不能移动了，那么我们应该怎么继续操作呢？什么，B[ ]整体向右移动？没错！这样我们又能得到，
哇，所有匹配都全部完成了诶！你看，这样是不是很能节省我们之前那种操作循环所需要的时间？其实KMP当中的预处理就是扮演了一个这样的角色，他告诉我们当A[i]!=B[j]时我们应该怎样整体移动B[ ]的数组，next预处理函数所做的只是查找当A[i]与B[j]不匹配时，A[i]之前的后m个元素与B[ ]数组开头的前m个元素顺序相同时的提取下标的操作，你看看之前的操作是不是这样进行操作的呢？