朴素字符串匹配算法

朴素方法测试模式P [1.......m]相对于文本T [1......n]的所有可能位置。 我们尝试平移量 s = 0, 1.......n-m，依次进行，并且对于每个平移量 s，比较 T [s+1.......s+m] 与 P [1......m]。

朴素算法使用一个循环查找所有有效的平移量，该循环检查每个可能的 s 值 (n - m +1) 的条件 P [1.......m] = T [s+1.......s+m]。

NAIVE-STRING-MATCHER (T, P)
 1. n ← length [T]
 2. m ← length [P]
 3. for s ← 0 to n -m
 4. do if P [1.....m] = T [s + 1....s + m]
 5. then print "Pattern occurs with shift" s

分析: 从 3 到 5 的这个 for 循环执行 n-m + 1 (结尾至少需要 m 个字符) 次，并且在迭代中，我们进行 m 次比较。 所以总复杂度是 O (n-m+1)。

示例

解决方案