F

分手后的思念是犯贱 2022-08-10 09:59 198阅读 0赞

## F ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

给出两串数字A\[ \]，B\[ \]，如果B是A的子串，那么输出B在A中第一次出现的位置，否则输出-1。

## 输入 ##

第一行，输入一个T，表明后面有几组数据。每组数据的第一行，输入两个数N、M (1 <= N <= 1000000, 1 <= M <= 10000)，N表示第一行数字的个数，M表示第二行数字的个数。接下来两行，分别输入A数列和B数列。

## 输出 ##

输出只有一行。如果数列B在数列A中出现过，输出数列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 10
    -1

## 提示 ##

## 来源 ##

zmx

## 示例程序 ##

#include<stdio.h>  
    #include<string.h>  
    #include<stdlib.h>  
    int  a[1000001],b[1000001];  
    int next[1000000];  
    void Next(int str[],int len)  
    {  
        next[0] = -1;  
        for(int j = 1 ; j < len ; j++)  
        {  
            int i = next[j-1];  
            while(str[j] != str[i+1] && i >= 0)  
            {  
                i = next[i];  
            }  
            if(str[j] == str[i+1])  
            {  
                next[j] = i+1;  
            }  
            else  
            {  
                next[j] = -1;  
            }  
        }  
    }  
    int kmp(int des[],int len1,int pat[],int len2)  
    {  
        Next(pat,len2);  
        int p=0,s=0;  
        while(p < len2  && s < len1)  
        {  
            if(pat[p] == des[s])  
            {  
                p++;s++;  
            }  
            else  
            {  
                if(p==0)  
                {  
                    s++;  
                }  
                else  
                {  
                    p = next[p-1]+1;  
                }  
            }  
        }  
        if(p < len2)  
        {  
            return -1;  
        }  
        return s-len2+1;  
    }  
    int main()  
    {  
    int i,j,n,m,k,t,l1,l2;  
    scanf("%d",&n);  
    while(n--)  
    {  
    scanf("%d %d",&m,&t);  
    {  
    for(i=0;i<m;i++)  
    scanf("%d",&a[i]);  
    for(i=0;i<t;i++)  
    scanf("%d",&b[i]);  
    k=kmp(a,m,b,t);  
    if(k!=-1)  
    printf("%d %d\n",k,k+t-1);  
    else  
    printf("%d\n",k);  
    }  
    }  
    }