大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/171736.html原文链接：https://javaforall.net
