[C++知识库]字符串匹配

题目

思路

1. KMP
2. 使用C++ find()函数

代码

• KMP方法

/*
Created by LZJ on 2022/2/24.
   字符串匹配问题
*/
#include<stdio.h>
#include<string.h>
#define N 110

//next数组
void getNext(int *Next,char *str){
   int j=0;
   Next[0]=0;

   for(int i=1;i<strlen(str);i++){
       while(j>0 && str[i]!=str[j])
           j=Next[j-1];
       if(str[i]==str[j]){
           j++;
       }
       Next[i]=j;
   }
}

char toBig(char a){
   if(a>='a'&&a<='z'){
       a+=('A'-'a');
   }
   return a;
}

int main(){
   int Next[N];
   char str[N];
   scanf("%s",str);
   //标记是否忽略大小写 0表示忽略，1表示不忽略
   int flag;
   scanf("%d",&flag);
   int num;
   scanf("%d",&num);

   getNext(Next,str);
   while(num--){
       char target[N];
       scanf("%s",target);
       if(strlen(target)<strlen(str)){
           continue;
       }

       for(int i=0,j=0;i<strlen(target);){
           if(flag==0){
               if(toBig(target[i])==toBig(str[j])){
                   i++;
                   j++;
               }else{
                   if(j==0){
                       i++;
                   }else if(j>0){
                       j=Next[j-1];
                   }
               }
           }else if(flag==1){
               if(target[i]==str[j]){
                   i++;
                   j++;
               }else{
                   if(j==0){
                       i++;
                   }else if(j>0){
                       j=Next[j-1];
                   }
               }
           }
           if(j==strlen(str)){
               printf("%s\n",target);
               break;
           }
       }

   }
   return 0;
}

• find()函数

#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;

int n;
string s1,s2;
//将字符串转化为全小写
void solve(string &s)
{
    for(int i=0;i<s.size();i++){
        if(s[i]>='A'&&s[i]<='Z')
            s[i]=s[i]-'A'+'a';
    }
}
int main()
{
    int flag;
    while(cin>>s1){
        scanf("%d",&flag);
        if(flag){
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                cin>>s2;
                if(s2.find(s1)!=s2.npos)//npos是一个很大的数,表示不存在 
                    cout<<s2<<endl;
            }
        }
        else{
            solve(s1);
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                cin>>s2;
                string s3=s2;
                solve(s2);
                if(s2.find(s1)!=s2.npos)//如果s2中存在s1 
                    cout<<s3<<endl;
            }
        }
    }
    return 0;
}

注意

一开始忘记在查询到有相比配的字符时，输出并且break，导致这个题一直没法100.