学步园

题目链接~~>

做题感悟：今天学习了一下KMP虽然还处于迷茫状态，但是照着模版很容易就把这题A了。

解题思路：KMP 裸题（可以用作模版）。

代码：

#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
const double PI = 3.1415926 ;
const double INF = 99999999 ;
const int MX =1000005 ;
int n ,m ;
int a[MX],b[MX],next[MX] ;
void getnext()  // 求next[] 数组
{
    int i=0,j=-1 ;
    next[0]=-1 ; 
    while(i<m-1)
    {
        if(j==-1||b[i]==b[j])// 重新匹配 || 两者相等比较下一个
        {
            i++ ;
            j++ ;
            next[i]=j ;
        }
        else   // b[i] != b[j]  则到有最多匹配的下标的下一个值去再匹配
               j=next[j] ;
    }
}
int KMP()
{
    int i=0,j=0 ;
    getnext() ;
    while(i<n)
    {
        if(j==-1||a[i]==b[j]) // 从头开始匹配||匹配成功继续比较下一对
        {
            i++ ;
            j++ ;
        }
        else
              j=next[j] ;
        if(j==m)  // 如果匹配成功返回起始匹配点
             return i-m+1 ;
    }
    return -1 ;
}
int main()
{
    int T ;
    scanf("%d",&T) ;
    while(T--)
    {
        scanf("%d%d",&n,&m) ;
        for(int i=0 ;i<n ;i++)
            scanf("%d",&a[i]) ;
        for(int i=0 ;i<m ;i++)
            scanf("%d",&b[i]) ;
        printf("%d\n",KMP()) ;
    }
    return 0 ;
}