大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
字符串匹配——枚举法
给定主串T和模式串P,返回P在T中首次出现的位置,如果P不存在于T中,返回-1。
这样的问题就是字符串匹配问题,这里先给出枚举法的思想。
设主串T的长度为n,模式串P的长度为m。
主串从0到n-m,每次选取连续的m个字符,跟模式串P的m个字符进行一一比较。
伪代码
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
实现代码
// 布鲁特逼近法也就是穷举法
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;
}
测试主程序
#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)
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/171736.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...