数据结构实验之串三：KMP应用

àì夳堔傛蜴生んèń 2022-07-15 04:12 171阅读 0赞

### 数据结构实验之串三：KMP应用 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

有n个小朋友，每个小朋友手里有一些糖块，现在这些小朋友排成一排，编号是由1到n。现在给出m个数，能不能唯一的确定一对值l和r(l <= r)，使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数？

#### Input ####

首先输入一个整数n，代表有n个小朋友。下一行输入n个数，分别代表每个小朋友手里糖的数量。

之后再输入一个整数m，代表下面有m个数。下一行输入这m个数。

#### Output ####

如果能唯一的确定一对l,r的值，那么输出这两个值，否则输出-1

#### Example Input ####

5
    1 2 3 4 5
    3
    2 3 4

#### Example Output ####

2 4

#### Hint ####

#### Author ####

windream

#include<bits/stdc++.h>
    using namespace std;
    int next[1000010];
    int str1[1000010];
    int str2[1000010];
    void get_next(int k)
    {
        int i=0;
        int j=-1;
        next[0]=-1;
        while(i<k)
        {
            if(j==-1||str2[i]==str2[j])
            {
                i++;
                j++;
                next[i]=j;
            }
            else
            {
                j=next[j];
            }
        }
    }
    
    int kmp(int n,int k,int m)
    {
        int i=m;
        int j=0;
        get_next(k);
    
        while(i<n&&j<k)
        {
            if(j==-1||str1[i]==str2[j])
            {
                i++;
                j++;
            }
            else
            {
                j=next[j];
            }
        }
        if(j>=k)
        {
                return i-k+1;
    
        }
        else
        {
    
            return -1;
        }
    }
    
    int main()
    {
        int n;
        int k;
        while(cin>>n)
        {
            for(int i=0;i<n;i++)
    
            {
                scanf("%d",&str1[i]);
            }
            cin>>k;
            for(int i=0;i<k;i++)
            {
                scanf("%d",&str2[i]);
            }
            int x=kmp(n,k,0);
            if(x!=-1)
            {
                int y=kmp(n,k,x+k-1);
                if(y==-1)
                {
                    printf("%d %d\n",x,x+k-1);
                }
                else
                {
                    printf("-1\n");
                }
            }
            else
            {
                printf("-1\n");
            }
    
        }
        return 0;
    
    
    }

ps:要确定唯一一个子串

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1844/pid/3311.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1844/pid/3311.html