目录
  1. 1. 字符串匹配01 Brute-Force 暴力求解
    1. 1.1. 思路
    2. 1.2. 代码实现
    3. 1.3. 算法分析
字符串匹配01 - Brute-Force算法

字符串匹配01 Brute-Force 暴力求解

问题:

​ 给定字符串 SS 和模板字符串 TT , 求 TT 是否在 SS 中出现过, 如果有, 则返回 TTSS 中第一次出现的位置.

思路

刚开始拿到这个问题, 很容易就会想到暴力的解法 - 即在 SS 中枚举, 尝试匹配模板串 TT , 即所谓的Brute ForceBrute \space Force 算法

具体步骤可以是:

  • 当前枚举的字符 chSch \in S
  • 从当前位置 (即字符 chch 的下标) 开始检查后续 T|T| 个字符
  • 如果从 chch 处开始的 T|T| 个字符组成的字符串与 TT 相等 , 则代表我们找到了需要匹配的模板串 , 否则, 当前位置向后移动, 回到步骤1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int brute_force_match(const std::string &S, const std::string &T) {
int n = S.length();
int m = T.length();

for (int i = 0; i <= n - m; ++i) {
for (int j = 0; j < m; ++j) {
if(S[i + j] != T[j])
break;
if (j == m - 1)
return i;
}
}

return -1;
}

算法分析

显然, 外层循环为O(n)\Omicron(n) , 内层为O(m)\Omicron(m), 则总时间复杂度为O(nm)\Omicron(nm)

文章作者: Twiliness
文章链接: https://twiliness.xyz/2019/10/07/String-Matching-01-Brute-Force/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Twilight Spring