前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >字符串匹配——枚举法[通俗易懂]

字符串匹配——枚举法[通俗易懂]

作者头像
全栈程序员站长
发布2022-09-24 14:19:47
4290
发布2022-09-24 14:19:47
举报

大家好,又见面了,我是你们的朋友全栈君。

字符串匹配——枚举法

给定主串T和模式串P,返回P在T中首次出现的位置,如果P不存在于T中,返回-1。

这样的问题就是字符串匹配问题,这里先给出枚举法的思想。

设主串T的长度为n,模式串P的长度为m。

主串从0到n-m,每次选取连续的m个字符,跟模式串P的m个字符进行一一比较。

伪代码

代码语言:javascript
复制
BruteForce(T, P)
01 for s <- 0 to n - m
02  j <- 0
03  // check if T[s...s+m-1] = p[0...m-1]
04  while T[s+j] = P[j] do
05      j <- j + 1
06      if j = m then return s;
07 return -1

实现代码

代码语言:javascript
复制
// 布鲁特逼近法也就是穷举法
int bruteForce(const string &T,const string &P) {
    // 主串的长度
    int n = T.length();
    // 模式串的长度
    int m = P.length();
    for(int i = 0; i <= n - m; i++) {
        // 比较串T[i...i+m-1]和P[0...m-1]
        for(int j = 0; j < m; j++) {
            // 匹配失败则T指向下一个元素
            // P从零开始
            if(T[i + j] != P[j]) {
                break;
            }
            // 在主串中找到模式串
            if(j == m - 1) {
                // 返回模式串在主串的最早出现位置
                return i;
            }
        }
    }
    // 未在主串中找到模式串
    return -1;
}

测试主程序

代码语言:javascript
复制
#include <iostream>
#include <string>

using namespace std;

// 布鲁特逼近法也就是穷举法
int bruteForce(const string &T,const string &P) {
    // 主串的长度
    int n = T.length();
    // 模式串的长度
    int m = P.length();
    for(int i = 0; i <= n - m; i++) {
        // 比较串T[i...i+m-1]和P[0...m-1]
        for(int j = 0; j < m; j++) {
            // 匹配失败则T指向下一个元素
            // P从零开始
            if(T[i + j] != P[j]) {
                break;
            }
            // 在主串中找到模式串
            if(j == m - 1) {
                // 返回模式串在主串的最早出现位置
                return i;
            }
        }
    }
    // 未在主串中找到模式串
    return -1;
}

/** IN at the thought of though OUT 7 **/
int main() {
    // 主串和模式串
    string T, P;
    while(true) {
        // 获取一行
        getline(cin, T);
        getline(cin, P);
        int res = bruteForce(T, P);
        if(res == -1) {
            cout << "主串和模式串不匹配。" << endl;
        } else {
            cout << "模式串在主串的位置为:" << res << endl;
        }
    }
    return 0;
}

算法分析

最坏情况

  • 外层循环:n-m
  • 内层循环:m
  • 总计(n-m)m = O(nm)

最好情况

  • n-m

完全随机的主串和模式串

  • O(n – m)

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/171736.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 字符串匹配——枚举法
    • 伪代码
      • 实现代码
        • 测试主程序
          • 算法分析
            • 最坏情况
            • 最好情况
            • 完全随机的主串和模式串
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档