coreBugZJ

此 blog 已弃。

KMP


字符串匹配的高效算法,理论就不说了,我的代码:


 1 template<class T>
 2 
 3 void KMPinit( const T * pat, int patLen, int * flink ){
 4 
 5         int j, k;
 6 
 7         flink[ 0 ] = -1;
 8 
 9         for( j = 1; j < patLen; ++j ){
10 
11                 k = flink[ j - 1 ];
12 
13                 while( ( k != -1 ) && ( pat[ j - 1 ] != pat[ k ] ) ){
14 
15                         k = flink[ k ];
16 
17                 }
18 
19                 flink[ j ] = k + 1;
20 
21         }
22 
23 }
24 
25 
26 
27 template<class T>
28 
29 int KMPmatch( const T * txt, int txtLen, const T * pat, int patLen, const int * flink, int matBegin = 0 ){
30 
31         int i = matBegin, j = 0;
32 
33         while( ( i < txtLen ) && ( j < patLen ) ){
34 
35                 while( ( j != -1 ) && ( txt[ i ] != pat[ j ] ) ){
36 
37                         j = flink[ j ];
38 
39                 }
40 
41                 ++j;
42 
43                 ++i;
44 
45         }
46 
47         return ( j >= patLen ? i - patLen : -1 );
48 
49 }
50 


posted on 2011-03-20 19:40 coreBugZJ 阅读(1272) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理