题128.2021秋周练习-3-10 串的模式匹配 (20 分)

一、题目

在这里插入图片描述

二、题解

本题考查字符串模式匹配，直接套kmp算法就好

#include <bits/stdc++.h>

using namespace std;

void getNext(string str,int next[])
{
    int j=0,k=-1;
    next[0]=-1;
    while(j<(int)str.length()-1)
    {
        if(k==-1||str[j]==str[k])
        {
            j++;
            k++;
            if(str[j]!=str[k])
            {
                next[j]=k;
            }
            else
            {
                next[j]=next[k];
            }
        }
        else
        {
            k=next[k];
        }
    }
}

int kmp(string str0,string str,int next[])
{
    int i=0,j=0;
    while(i<(int)str0.length()&&j<(int)str.length())
    {
        if(j==-1||str0[i]==str[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    }
    if(j==(int)str.length())
    {
        return i-j;
    }
    else
    {
        return -1;
    }
}

int main()
{
    string str0;
    cin>>str0;
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        string str;
        cin>>str;
        int next[100001];
        getNext(str,next);
        int pos=kmp(str0,str,next);
        if(pos==-1)
        {
            printf("Not Found\n");
        }
        else
        {
            for(int j=pos;j<str0.length();j++)
            {
                cout<<str0[j];
            }
            putchar('\n');
        }
    }
}

对于这个代码有个要十分注意的地方，就是string.length()的数据类型，它是unsigned int，它的级别高于int，所以在作为int的i，j和length比大小的时候，i，j都会被强转为unsigned int，此时如果有取-1或者其他负数的情况，它强转之后便会转成一个超级大的数，导致-1<length值为0。综上，我们在此处进行那个比大小操作的时候应该把length强转成int