朴素字符串匹配算法

深藏阁楼爱情的钟 2022-04-14 02:10 187阅读 0赞

最简单的字符串匹配方法，传说中的在特殊情况的暴力求解：

伪代码：

naive_string_matcher(t,p):
       n=len(t)
       m=len(p)
       for s =0 to n-m:
              if p[1..m]==t[s+1..s+m]:
                     print("success!")

具体的代码：

str1 = 'aabacgaabgcaab'
    str2 = 'aab'
    
    
    def naive_string_match(str1, str2):
        n1 = len(str1)  # 8
        n2 = len(str2)  # 3
        result = []
        index = 0
        for s in range(n1 - n2 + 1):  # 0 1 2
            # print(s)
            for j in range(n2):
                if str1[s + j] == str2[j]:
                    index += 1
                else:
                    index = 0
                    break
            if index == n2:
                result.append(s)
    
        return result
    print("返回匹配点的下标：")
    print(naive_string_match(str1, str2))

运行结果

返回匹配点的下标：  
\[0, 6, 11\]

c语言版本：

#include<stdio.h>
    #include<string.h>
    int main(void)
    {    
         char str1[50]="aabacgaabgcaab";
         char str2[12]="acg";    
         int  m=strlen(str1),n=strlen(str2);// n是小字符串，m是大字符串
         int len=m-n+1;
         for(int i=0;i<len;i++){
              int index=0;
              for(int j=0;j<n;j++){
                  if(str1[i+j]==str2[j])  index+=1;
              }  
              if(index==n){
                    printf("true");  
                    break;
              }  
         }
        
    }

发表评论取消回复

表情：

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

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

相关阅读

相关字符串匹配算法

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

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

相关 Brute Force(暴力破解/朴素匹配算法)

在字符串的匹配时，单模式串的匹配，最有效或者最简单的就是暴力破解. public class BF {

我会带着你远行/ 2022年12月21日 14:55/ 0 赞/ 150 阅读

相关 408数据结构——串的模式匹配：朴素模式匹配算法（暴力匹配）+KMP算法

> 王道408数据结构第四章，串的模式匹配。 > 考试中不大可能考察KMP的算法代码，也不会考察KMP的优化，需要掌握手动求KMP的next数组，以及掌握朴素模式匹配算法及

￡神魔★判官ぃ/ 2022年10月09日 00:33/ 0 赞/ 261 阅读

相关【字符串】朴素串匹配

include <stdio.h> void main() { int i = 0; int j = 0; in

痛定思痛。/ 2022年08月25日 09:18/ 0 赞/ 174 阅读

相关字符串匹配算法

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

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

相关算法——字符串匹配之朴素算法

前言本文介绍的是字符串匹配最简单的算法--朴素字符串匹配算法。该算法的原理非常简单，就是通过一个循环找到所有有效偏移，即对[![0 \\leqslant s < n-

╰+攻爆jí腚メ/ 2022年08月13日 00:47/ 0 赞/ 178 阅读

相关字符串匹配算法

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

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

相关算法字符串匹配之朴素算法和KMP算法及JAVA代码实现

暴力匹配算法假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？如果用暴力匹配的思路，并假设现在文本串S匹配到 i

以你之姓@/ 2022年06月15日 11:55/ 0 赞/ 178 阅读

相关朴素字符串匹配算法

最简单的字符串匹配方法，传说中的在特殊情况的暴力求解：伪代码： naive_string_matcher(t,p): n=len(t)

深藏阁楼爱情的钟/ 2022年04月14日 02:10/ 0 赞/ 188 阅读

相关字符串匹配算法

BF算法（Brute Force）暴力匹配算法，在主串和模式串每次比较都只前进一个位置，进行比较。 ![18721752-e54c845998d33231.png][

电玩女神/ 2021年10月01日 09:16/ 0 赞/ 414 阅读