字符串近似匹配算法

2012/6/13 11:40:00  请友读忠(更多)  E界MRP开发下载网  265阅

字符串的近似匹配，就是允许在匹配时有一定的误差，比如在字串“以前高手好久不见”中找“以前是高手”也能成功。具体地说，错误可以有三种类型：加字符（以前也是高手）、漏字符（以前高手）和替换字符（以前石膏手）。下面的函数在text中查找子串pat，最多允许有k个错误。返回的是匹配的终点（我还没想好如何确定起点，呵呵）。
至于算法的原理，现在一下子说不清楚，只能说这是一个非确定性有限自动机，以后有时间的话再详细介绍。有兴趣的话可以自己去看文章《faster approximate string matching》, algorithmica (1999) 23: 127-158。

算法的限制：(m-k)*(k+2) 0);
assert((m-k)*(k+2)>j)&onekp1);
__int64 x = (d>>(k+2))|tc;
d=((d>1)&din;
if((d & g) == 0)
return (**)s;
if(d != din)
c = *s++;
}
while ( d != din && c);
}
if (c)
c = *s++;
}
return null;
}