朴素字符串匹配算法朴素字符串匹配算法|算法设计

幼稚的方法测试模式P [1 … … . m]相对于文本T [1 … … n]的所有可能位置。我们依次对每个移位s尝试移位s = 0, 1 … … . n-m。比较T [s + 1 … … . s + m]与P [1 … … m]。
朴素算法使用一个循环来查找所有有效移位, 该循环检查n-m的每一个的条件P [1 … … . m] = T [s + 1 … … . s + m] +1可能的s值。

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）。
例：