字符串匹配算法
我们经常要在一段文本中某个特定的位置找出某个特定的字符或模式。由此,便产生了字符串的匹配问题。
假设文本是一个长度为n的数组T[1...n],模式是一个长度为m<=n的数组P[1....m]。
简单字符串匹配
目标是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出现。
该模式仅在文本中出现了一次,在位移s=3处。位移s=3是有效位移。
n = length(T)m = length(P)
int flag=1;for(s = 0 ; s < n-m ; s++)
{
flag=1;
for(i = 0 ; i < m ; i++)
{
if (P[i] != T[s+i]) {flag=0;break;}
}
if(flag) {cout << s; break;}
}
简单的字符串匹配算法用一个循环来找出所有有效位移,该循环对n-m+1个可能的每一个s值检查条件
P[0....m-1]=T[s....s+m-1]
简单字符串匹配算法,上图针对文本T=acaabc 和模式P=aab。
n-m+1个可能的位移s中的每一个值,比较相应的字符的循环。
所以,在最坏情况下,此简单模式匹配算法的运行时间为O((n-m+1)m)。
对于目的字串T是banananobano,要匹配的字串P是nano的情况
只要P字串第一个字符先和T字串的第一个字符比较,如果相同就比较下一个,如果不同就把P右移一下,之后再从P的每一个字符比较,这个算法的运行过程如下图。
nano
时间复杂度是O(m * n)
KMP算法
算法导论之字符串匹配算法 来自淘豆网m.daumloan.com转载请标明出处.