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

叁歲伎倆 2022-07-15 05:10 125阅读 0赞

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

#include<iostream>
    #include<cstring>
    using namespace std;
    char s1[1000005],s2[1000005];
    int next[1000005],k=0;
    void get_next()
    {
        int i=0,j=-1;
        next[0]=-1;
        while(s2[i]!='\0')
        {
            if(j==-1||s2[i]==s2[j])
            {
                i++;j++;
                //if(s[i]!=s[j])
                next[i]=j;
               // else next[i]=next[j];
            }
            else j=next[j];
        }
    }
    int KMP()
    {
        int i=0,j=0;
        get_next();
        int len1=strlen(s1);
        int len2=strlen(s2);
        while(i<len1&&j<len2)
        {
            if(j==-1||s1[i]==s2[j])
            {
                ++i;++j;
            }
            else j=next[j];
        }
        if(j>=len2)
            cout<<"YES"<<endl;
         else   cout<<"NO"<<endl;
    }
    int main()
    {
         while(cin>>s1>>s2)
             {
                  KMP();
             }
         return 0;
    }

[Link 1]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1844/pid/2125

发表评论取消回复

表情：

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

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

相关阅读

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

字符串（简称串）是一种特殊的线性表，它的每个结点仅由一个字符组成。（也可以称–有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 赞/ 100 阅读

相关数据结构实验之串三：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 赞/ 130 阅读

相关数据结构(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 阅读