数据结构实验之串二：字符串匹配

古城微笑少年丶 2022-11-21 11:45 100阅读 0赞

## 数据结构实验之串二：字符串匹配 ##

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

Input  
输入包含多组数据，每组测试数据包含两行，第一行代表string1，第二行代表string2，string1和string2中保证不出现空格。(string1和string2大小不超过100字符)

Output  
对于每组输入数据，若string2是string1的子串，则输出"YES"，否则输出"NO"。

Sample  
Input  
abc  
a  
123456  
45  
abc  
ddd  
Output  
YES  
YES  
NO

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    char a[1000010],b[1000010];
    int next[1000010];
    void fnext(int len)
    {
        
        int i=0,j=-1;
        next[0]=-1;
        while(i<len)
        {
        
            if(j==-1||a[i]==a[j])
            {
        
                i++;
                j++;
                next[i]=j;
            }
            else
                j=-1;
        }
    }
    void kmp(int len1,int len2)
    {
        
        int i=0,j=0;
        while(i<len1&&j<len2)
        {
        
            if(j==-1||a[i]==b[j])
            {
        
                i++;
                j++;
            }
            else
                j=next[j];
        }
        if(j==len2)
            printf("YES\n");
        else
            printf("NO\n");
    }
    int main()
    {
        
        while(~scanf("%s %s",a,b))
        {
        
            int len1=strlen(a);
            int len2=strlen(b);
            fnext(len2);
            kmp(len1,len2);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关【数据结构】串（字符串）

字符串（简称串）是一种特殊的线性表，它的每个结点仅由一个字符组成。（也可以称–有0个或多个字符组成的有限序列叫做串）记作： S = “a1a2a3…an”；

╰+攻爆jí腚メ/ 2023年09月23日 19:16/ 0 赞/ 81 阅读

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

数据结构实验之串三：KMP应用 Description 有n个小朋友，每个小朋友手里有一些糖块，现在这些小朋友排成一排，编号是由1到n。现在给出m个数，能不能唯一的确

红太狼/ 2022年11月21日 11:50/ 0 赞/ 141 阅读

相关数据结构实验之串二：字符串匹配

数据结构实验之串二：字符串匹配 Description 给定两个字符串string1和string2，判断string2是否为string1的子串。 Input

古城微笑少年丶/ 2022年11月21日 11:45/ 0 赞/ 101 阅读

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

数据结构实验之串三：KMP应用 Time Limit: 1000MS Memory limit: 65536K 题目描述有n个小朋友，每个小朋友手里

短命女/ 2022年09月25日 01:26/ 0 赞/ 140 阅读

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

数据结构实验之串三：KMP应用 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述有n

末蓝、/ 2022年08月14日 05:51/ 0 赞/ 158 阅读

相关 SDUTACM 数据结构实验之串二：字符串匹配

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

墨蓝/ 2022年07月15日 13:08/ 0 赞/ 118 阅读

相关 2125 数据结构实验之串二：字符串匹配

[数据结构实验之串二：字符串匹配][Link 1] 这题与串一代码基本一致 include<iostream> include<cstring>

叁歲伎倆/ 2022年07月15日 05:10/ 0 赞/ 126 阅读

相关数据结构实验之串二：字符串匹配

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

素颜马尾好姑娘i/ 2022年07月11日 01:58/ 0 赞/ 131 阅读

相关数据结构(6) 串 [二] ( KMP模式匹配算法 )

KMP模式匹配算法（朴素算法的升级版本）原理：主串 S： “abcdefgab”找到子串T “abcdex” 的位置如果采用朴素算法，前5个字母，两个串完全

逃离我推掉我的手/ 2022年02月03日 06:55/ 0 赞/ 313 阅读

相关串结构练习——字符串匹配

题目描述给定两个字符串string1和string2，判断string2是否为string1的子串。输入输入包含多组数据，每组测试数据包含两行，

￡神魔★判官ぃ/ 2021年06月24日 13:58/ 0 赞/ 368 阅读