计算机问题求解一论题4-11 串匹配 2017年5月3日
计算机问题求解 – 论题4-11 - 串匹配 2017年5月3日
问题1： 什么是string-matching problem,直观上？形式上？
string-matching problem
text T a b c a a a b a b a S=3 pattern a a we say that pattern P occurs with shift s in text T (or,equivalently,that pattern P occurs beginning at position s+1 in text T)if 0≤s≤n-m and T5+l.s+m=P[l.m(that is,.ifT5+j】=P[Ujl,for 1jm).If P occurs with shift s in T,then we call s a valid shift;otherwise, we call s an invalid shift.The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T
text T a b a b a a b a b a c S=3 pattern P a b a a Algorithm Preprocessing time Matching time Naive 0 O(n-m+1)m) Rabin-Karp ⊙(m) O(n-m+1)m) Finite automaton O(mΣ) ⊙(n) Knuth-Morris-Pratt ⊙(m) ©(n)
最容易想到的算法 a a a b a a a b c a a a b a a a b S=0 =3 a b a b 问题2： 为什么称它为nave”算法？
最容易想到的算法