数据结构实验之串一：KMP简单应用

àì夳堔傛蜴生んèń 2022-05-08 12:42 131阅读 0赞

### Problem Description ###

给定两个字符串string1和string2，判断string2是否为string1的子串。

Input

输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。

Output

对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。

Sample Input

abc
    a
    123456
    45
    abc
    ddd

Sample Output

1
    4
    -1

tips:快被这题逼疯了

while(i<strlen(b))
        {
            if(j==-1||b[i]==b[j])
            {
                ne[++i]=++j;
            }
            else
                j=ne[j];
        }

一开始这样写while循环一直超时，找半天找不出来，超时的原因也很简单就是写里面的时候每次循环的时候都会扫描一遍字符串的长度.........这点东西都看不出来我真是蠢到家。后来改一下遍历一遍就可以了：

#include<bits/stdc++.h>
    using namespace std;
    int ne[1000000];
    char a[1000000],b[1000000];
    void getnext()
    {
        int i=0,j=-1;
        ne[0]=-1;
    int k=strlen(b);
        while(i<k)
        {
            if(j==-1||b[i]==b[j])
            {
                ne[++i]=++j;
            }
            else
                j=ne[j];
        }
    }
    void kmp()
    {
        int i=0,j=0;
        int len1=strlen(a);
        int len2=strlen(b);
        while(i<len1&&j<len2)
        {
            if(j==-1||a[i]==b[j])
            {
                ++i;
                ++j;
            }
            else
                j=ne[j];
        }
        if(j==len2)
           printf("%d\n",i-len2+1);
        else
            printf("-1\n");
    }
    int main()
    {
        while(gets(a))
        {
            gets(b);
            getnext();
            kmp();
        }
        return 0;
    }

因为最近在学python所以我用python3写了一个（没想到还真过了）：

flag=1;
    while flag==1:
        str1=input()
        str2=input()
        a=str1.find(str2)
        if a!=-1:
            print(a+1)
        else :
            print(-1)

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用 Description 给定两个字符串string1和string2，判断string2是否为string1的子串。 Inpu

桃扇骨/ 2022年11月21日 07:04/ 0 赞/ 89 阅读

相关数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定两个

你的名字/ 2022年08月10日 09:55/ 0 赞/ 97 阅读

相关数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用 Time Limit: 1000MS Memory limit: 65536K 题目描述给定两个字符串strin

╰半夏微凉°/ 2022年07月16日 23:19/ 0 赞/ 98 阅读

相关数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][]

谁践踏了优雅/ 2022年07月15日 03:37/ 0 赞/ 117 阅读

相关数据结构实验之串一：KMP简单应用

Problem Description 给定两个字符串string1和string2，判断string2是否为string1的子串。 Input 输入包含多组数据，每组

川长思鸟来/ 2022年07月12日 06:23/ 0 赞/ 104 阅读

相关数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Proble

阳光穿透心脏的1/2处/ 2022年07月12日 06:11/ 0 赞/ 118 阅读

相关数据结构实验之串一：KMP简单应用

数据结构实验之串一：KMP简单应用 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 给定两个

男娘i/ 2022年07月11日 16:06/ 0 赞/ 110 阅读

相关数据结构实验之串一：KMP简单应用

Problem Description 给定两个字符串string1和string2，判断string2是否为string1的子串。 Input 输入包含多组数

灰太狼/ 2022年07月11日 01:58/ 0 赞/ 115 阅读

相关数据结构实验之串一：KMP简单应用

Problem Description 给定两个字符串string1和string2，判断string2是否为string1的子串。 Input 输入包含多组数据，每

àì夳堔傛蜴生んèń/ 2022年05月08日 12:42/ 0 赞/ 132 阅读

相关数据结构实验之串一：KMP简单应用

Problem Description 给定两个字符串string1和string2，判断string2是否为string1的子串。 Input 输入包含多组数据，每组

约定不等于承诺〃/ 2022年04月18日 04:20/ 0 赞/ 119 阅读