字符串匹配

喜欢ヅ旅行 2022-07-21 01:49 181阅读 0赞

题目：子串匹配母串，如果匹配，输出子串匹配的起始位置，否则输出-1。？可以代表一个字符，\*代表一个或者多个。  
从键盘输入，先输入子串，再输入母串。子串母串长度均小于20。运行时间和内存无限制。  
  
一开始打算用KMP或BM算法来做，考试电脑可以上网，可以去查，但是子串有了通配符，next函数好像无法求（还没想到），所以暴力求解，可惜当时没调试出来。  
思路：用一个find函数来找。  
int find(char \*substr,int start1,char \*str,int start2)  
其中，start1是子串匹配的其实位置，start2是母串匹配的其实位置。加上这两个参数是为了递归调用，如果子串遇到通配符\*，要递归调用（\*后面的再和母串某个位置之后的串匹配）。大概思路就是这样，要调试好，还是要花一些时间。  
代码如下：

#include<iostream>
    using namespace std;
    int find(char *substr,int start1,char *str,int start2)
    {
    int length1=strlen(substr);//子串长度
    int length2=strlen(str);//母串长度
    int result=-1;//最终要返回的结果
    int current;
    for(int i=start2;i<=length2;i++)//start2为母串搜索的其实位置
    {
    if(i==length2+1)//搜索失败
    return -1;
    result=i;
    current=i;
    for(int k=start1;k<=length1;k++)//start1为子串搜索的其实位置
    {
    if(k==length1-1)
    return result;
    if(substr[k]==str[current]||substr[k]=='?')
    {
    current++;
    }
    else if(substr[k]=='*')//遇到*通配符，代表任何一个或者多个或者0个字符
    {
    if(-1==find(substr,k+1,str,current))
    return -1;
    else return result;
    }
    else break;
    }
    }
    }
    int main()
    {
    char *substr=(char*)malloc(21*sizeof(char));
    char *str=(char*)malloc(21*sizeof(char));
    cin>>substr;
    cin>>str;
    cout<<find(substr,0,str,0);
    return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关字符串匹配算法

主要算法：BF RK BM KMP Sunday算法 BF ：Brute Force，暴力匹配算法字符串A中查找字符串B 主串：A，长度n 模式串：B，长度m

女爷i/ 2023年06月23日 02:56/ 0 赞/ 144 阅读

相关 java字符串匹配dp_字符串匹配问题

递归解法 import java.util.\; public class Main \{ //isValid public static boolean isValid

亦凉/ 2022年11月06日 13:58/ 0 赞/ 208 阅读

相关 huawei-字符串匹配

题目描述写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字母，然后输出输入字符串中该字母的出现次数。不区分大小写输入描述: 第一行输入一个由字母和数

妖狐艹你老母/ 2022年11月03日 04:08/ 0 赞/ 169 阅读

相关字符串匹配算法

字符串匹配算法本文转自：[Yushneng][Yushneng] ：[http://blog.rainy.im/2016/04/24/string-find/][h

╰半夏微凉°/ 2022年08月21日 08:42/ 0 赞/ 165 阅读

相关字符串匹配

题目：子串匹配母串，如果匹配，输出子串匹配的起始位置，否则输出-1。？可以代表一个字符，\代表一个或者多个。从键盘输入，先输入子串，再输入母串。子串母串长度均小于20。运

喜欢ヅ旅行/ 2022年07月21日 01:49/ 0 赞/ 182 阅读

相关字符串匹配算法

记录两个字符串匹配算法：KMP和BM算法。转载地址：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%

╰+攻爆jí腚メ/ 2022年06月16日 09:27/ 0 赞/ 209 阅读

相关字符串匹配

. -- 用于匹配任意一个字符, 除了换行符 \-- 用来匹配它前面字符的任意多次 ^ -- 匹配行首 $ -- 用来匹配行尾 \[char\]-匹配中括号字符

野性酷女/ 2022年01月05日 22:23/ 0 赞/ 260 阅读

相关 Hash字符串匹配

hash字符串匹配即把固定长度的字符串转化为hash值进行匹配，这种匹配方式在大量数据的情况下是有误差的，大约万分之四五左右，这是因为hash值是通过字符和公式计算出来的，不同

╰+哭是因爲堅強的太久メ/ 2021年09月23日 01:14/ 0 赞/ 407 阅读

相关字符串匹配（java）

字符串匹配字符串匹配可以用到蛮力法。对于字符串s和t，若t是s的子串，返回t在s中的位置（t的首字符在s中的下标），否则返回-1. 采用的是穷举法，从s的

野性酷女/ 2021年07月25日 00:49/ 0 赞/ 585 阅读

相关 CCF 字符串匹配

一.问题描述给出一个字符串和多行文字，在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项：当选项打开时，表示同一个字母的大写和小写看作不同的字符；当选项

清疚/ 2021年06月24日 14:36/ 0 赞/ 436 阅读