Number Sequence

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 22067    Accepted Submission(s): 9434 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

这里介绍一下KMP算法，它是求两个串匹配问题，术语叫串的模式匹配

即给出两个字符串a，b，求出一个数k(假设一定存在)，使得所有的b[i] = a[k+i]（一般是a串比b串长）

起初是求字符串的，但是字符串和数组基本一样，所以求数字序列也可以，拿字符串来讲解

序列A：babababc 

序列B：ababc

以这个为例，next[0]表示B[0]与A[0]不匹配时，以A[1]为新起点应与B的哪一位字符开始比较，显然要从B[0]，即从头开始，next[0]=0

而便于后边的计算，将next[0]初始化为-1

如：babababc        --->     babababc

        ababc                            ababc   

next[4]时，表示B[0]到B[3]均与A某一段匹配，这时A[5]与B[2]开始匹配就可以了，next[4] = 2

如：babababc        --->     babababc

          ababc                               ababc 

明显的next[i]表示类似（不知道怎么表达，就类似吧）上述B串的前i项重复的长度

无， 即A的某个字符与B[0]都不同，下次肯定还要从头开始

a，重复是0，即下次匹配依旧从头开始

ab，重复是0，即下次匹配依旧从头开始

aba，重复是1，即下次匹配从b即B[1]开始

abab，重复是2，即下次匹配从a即B[2]开始

ababc，完全匹配

就是i表示B[0]到B[i]与A串某一段完全匹配，但B[i+1]不匹配，0<=j<=i,i<B串的长度

 0                1               2           .........         j

  |                 |                |                |             |

i-j             i-j+1        i-j+2        .........          i                    这样对应的关系，完全相等的最长长度，即上述不可描述的重复长度

void Getnext(){ int i, j; i = 0; next[0] = j = -1; while(i < S-1){ if(j == -1 || s[i] == s[j]){ i++; j++; next[i] = j; } else{ j = next[j]; } } } 核心代码就是这个了，next[j]就是前j项满足上述重复的长度，很容易理解，不然找几组数据代入试一下，就明白了

核心只与短的那个串有关，与被查找的长串即主串无关

有时候看代码比看长篇大论的描述理解的要快

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define maxn 10010 #define Maxn 1000010 #define inf 0x3f3f3f3f #define mes(a, b) memset(a, b, sizeof(a)) int l[Maxn], s[maxn], next[maxn]; int L, S; void Getnext(){ int i, j; i = 0; next[0] = j = -1; while(i < S-1){ if(j == -1 || s[i] == s[j]){ i++; j++; next[i] = j; } else{ j = next[j]; } } } int kmp(){ int i, j; i = j = 0; while(i < L){//依据next的优化进行遍历 if(j == -1 || s[j] == l[i]){ i++; j++; } else{ j = next[j]; } if(j == S){ return i-S+1; } } return -1; } int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d%d", &L, &S); for(int i = 0; i < L; i++){ scanf("%d", &l[i]); } for(int i = 0; i < S; i++){ scanf("%d", &s[i]); } if(L < S){ printf("-1\n"); continue; } Getnext(); printf("%d\n", kmp()); } return 0; }

给出串的模板，其实一样的，只是把int改成char而已

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define maxn 10010 #define inf 0x3f3f3f3f #define mes(a, b) memset(a, b, sizeof(a)) char l[maxn], s[maxn]; int next[maxn]; int L, S; void Getnext(){ int i, j; i = 0; next[0] = j = -1; while(i < S-1){ if(j == -1 || s[i] == s[j]){ i++; j++; next[i] = j; } else{ j = next[j]; } } } int kmp(){ int i, j; i = j = 0; while(i < L){ if(j == -1 || s[j] == l[i]){ i++; j++; } else{ j = next[j]; } if(j == S){ return i-S; } } return -1; } int main(){ while(~scanf("%s%s", l, s)){ L = strlen(l); S = strlen(s); Getnext(); printf("%d\n", kmp()); } return 0; }