首页 > 编程语言 >串模式匹配-BF算法

串模式匹配-BF算法

时间:2023-10-12 14:56:36浏览次数:56  
标签:主串 BF ch string int 算法 length SString 模式匹配

一种暴力的串匹配算法。
指定主串中查找的起始位置。用两个指针分别遍历主串和子串,如果到达串尾就结束。 当遇到子串与主串不匹配时,通过把主串指针回溯到当前起始字符的下一个字符来重新开始匹配。

实现代码如下。

#include<iostream>
using namespace std;

#define MAXLEN 255

typedef struct {
    char ch[MAXLEN + 1]; // 谨防数组越界!!!之前某次写循环队列,
	//因为数组开的不够大,导致输入的字符串结束符没地方存,狂调一节课
    int length;
} SString;

void input_string(SString &s, SString &t) {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> s.ch[i];
    s.length = n;
    for(int i = 1; i <= m; i++) cin >> t.ch[i];
    t.length = m;
}

void out_string(SString s) {
    for(int i = 1; i <= s.length; i++) cout << s.ch[i] << " ";
    cout << endl;
} // 其实并没有用到这个函数

int index_bf(SString s, SString t, int pos) {
    int i = pos, j = 1;
    while(i <= s.length && j <= t.length) {
        if(s.ch[i] == t.ch[j]) i++, j++; // 如果匹配就比较下一位
        else i = i - j + 2, j = 1; // 如果不匹配 回溯主串指针 把子串指针拉到开头
    } 
    if(j > t.length) return i - t.length;
    else return 0;
}

int main() {
    SString s, t;
    input_string(s, t);
    cout << index_bf(s, t, 1);
    return 0;
}

时间复杂度:最好O(n + m) 最坏O(m * n)

标签:主串,BF,ch,string,int,算法,length,SString,模式匹配
From: https://www.cnblogs.com/iszxh/p/17759451.html

相关文章

  • 简单易学的机器学习算法——Latent Dirichlet Allocation(理论篇)
    引言LDA(LatentDirichletAllocation)称为潜在狄利克雷分布,是文本语义分析中比较重要的一个模型,同时,LDA模型中使用到了贝叶斯思维的一些知识,这些知识是统计机器学习的基础。为了能够对LDA原理有清晰的认识,也为了能够对贝叶斯思维有全面的了解,在这里对基本知识以及LDA的相关知识进......
  • Lnton羚通视频分析算法平台工地劳务实名制人脸识别管理方案
    Lnton羚通的算法算力云平台是一款优秀的解决方案,具有突出的特点。它提供高性能、高可靠性、高可扩展性和低成本的特性,使用户能够高效地执行复杂计算任务。此外,平台还提供丰富的算法库和工具,并支持用户上传和部署自定义算法,提升了平台的灵活性和个性化能力。在建筑工地场景中,施工人......
  • Spring MVC 与 Spring Webflux 性能测试,谁更强?
    如果你已经使用Spring一段时间或者是编程初学者,你一定听说过使用响应式编程比传统的线程池风格更好。自Spring诞生以来,开发者创建Java企业应用程序就变得更加容易。它提供了在企业环境中使用Java语言所需的一切,支持Groovy和Kotlin作为JVM上的替代语言,并且可以根据......
  • 交通标志识别系统python+TensorFlow+算法模型+Django网页+数据集
    一、介绍交通标志识别系统。技术涉及:Python编程语言开发TensorFlow搭建算法模型对数据集进行训练得到一个精度较高的模型文件Django开发网页端界面平台实现对58种交通标志图片进行识别二、效果图片展示三、演示视频and代码视频+代码+介绍:https://s7bacwcxv4.feishu.......
  • 算法:树链剖分
    去年就看过树链剖分的视频了,当时连树状数组,线段树都没学,对树的dfs也一知半解,所以基本完全听不懂。昨天又重新看了一般,感觉思路挺简单,应该比线段树简单吧,从用树链剖分求LCA来看确实是这样的,但是没有想到的是用线段树维护树链剖分。QAQ这应该是我打过最长的代码吧!(3K)树链剖分......
  • 【算法】游戏中的学习,使用c#面向对象特性控制游戏角色移动
    最近,小悦的生活像是一首繁忙的交响曲,每天忙得团团转,虽然她的日程安排得满满当当,但她并未感到充实。相反,她很少有时间陪伴家人,这让她感到有些遗憾。在周五的午后,小悦的哥哥突然打来电话,他的声音里充满了焦虑。“小悦,我有个事情想拜托你。”哥哥的声音传来。小悦不禁有些疑惑,哥哥......
  • WPF 笔迹算法 从点集转笔迹轮廓
    本文将告诉大家一些笔迹算法,从用户输入的点集,即鼠标轨迹点或触摸轨迹点等,转换为一个可在界面绘制显示笔迹画面的基础数学算法。尽管本文标记的是WPF的笔迹算法,然而实际上本文更侧重基础数学计算,理论上可以适用于任何能够支持几何绘制的UI框架上,包括UWP或WinUI或UNO或MA......
  • 基于亚奈奎斯特采样和SOMP算法的平板脉冲响应空间插值matlab仿真
    1.算法运行效果图预览 2.算法运行软件版本matlab2022a 3.算法理论概述     平板脉冲响应(PulseResponse)是通信和雷达等领域中的重要参数,它描述了信号在空间中传播的特性。在现实应用中,获取完整的脉冲响应通常是耗时且昂贵的。基于亚奈奎斯特采样和SOMP算法的平板脉......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素
    704.二分查找链接:https://leetcode.cn/problems/binary-search/description/思路:关键是定义清楚区间边界,想清楚middle在计算中是否可能取到左边界or右边界。若采用闭区间,则middle可能等于左/右边界值。27.移除元素链接:https://leetcode.cn/problems/remove-element/思路:暴......
  • 弗洛伊德(Floyd's)算法—解决最短路径经典算法
    弗洛伊德算法(Floyd'salgorithm)是一种用于解决图中最短路径问题的经典算法。由美国计算机科学家罗伯特·弗洛伊德于1962年提出,该算法通过动态规划的思想,在图中寻找任意两个节点之间的最短路径,具有广泛的应用。本文将详细介绍弗洛伊德算法的原理、实现细节以及应用案例。四、复杂度......