字符串匹配 - 模式预处理：朴素算法（Naive)(暴力破解)
大约 2 分钟
字符串匹配 - 模式预处理：朴素算法（Naive)(暴力破解)
朴素的字符串匹配算法又称为暴力匹配算法（Brute Force Algorithm），最为简单的字符串匹配算法。
算法简介
朴素的字符串匹配算法又称为暴力匹配算法（Brute Force Algorithm），它的主要特点是：
- 没有预处理阶段；
- 滑动窗口总是后移 1 位；
- 对模式中的字符的比较顺序不限定，可以从前到后，也可以从后到前；
- 匹配阶段需要 O((n - m + 1)m) 的时间复杂度；
- 需要 2n 次的字符比较；
很显然，朴素的字符串匹配算法 NAIVE-STRING-MATCHER 是最原始的算法，它通过使用循环来检查是否在范围 n-m+1 中存在满足条件 P[1..m] = T [s + 1..s + m] 的有效位移 s。
伪代码如下：
NAIVE-STRING-MATCHER(T, P)
n ← length[T]
m ← length[P]
for s ← 0 to n - m
do if P[1 .. m] = T[s + 1 .. s + m]
then print "Pattern occurs with shift" s
如上图中，对于模式 P = aab 和文本 T = acaabc，将模式 P 沿着 T 从左到右滑动，逐个比较字符以判断模式 P 在文本 T 中是否存在。
可以看出，NAIVE-STRING-MATCHER 没有对模式 P 进行预处理，所以预处理的时间为 0。而匹配的时间在最坏情况下为 Θ((n-m+1)m)，如果 m = [n/2]，则为 Θ(n2)。
图例分析
假设有两个字符串：
- M="abcdefabcdx";
- T="abcdx";
想要找到T串在M串中的位置，要怎么找呢？
也就是说，从主串M的第一个字符开始分别与子串从开头进行比较，当发现不匹配时，主串回到这一轮开始的下一个字符，子串从头开始比较。直到子串所有的字符都匹配，返回所在主串中的下标。
算法复杂度
假设S的长度是m，T的长度是n，暂不考虑pos，从字符串S的开头开始比较。
- 最好的情况是第一次就匹配了，需要比较的次数是n.
- 最坏的情况下，就是上面举的这种例子，需要把整个字符串都比较完，从下面的代码中就体现为把两层循环都跑了一遍。这时候，比较的次数就是t*(s-t+1).
所以这个算法的(最坏)时间复杂度就是o(t(s-t+1))，近似为o(n2).