C++ kmp算法模板代码解读

C++编程语言中的模板应用是一个比较复杂的应用技术，我们今天就先从C++ kmp算法模板的基本应用开始学习，从而加深我们对这方面知识的认识程度，方便将来的应用，提高编程效率。

在使用的时候加上这两行代码就行了

 
 
 

  
  
  
#include < vector>   
  
  
  
using namespace std; 
 
 
 

C++ kmp算法模板参数说明 #t#

const T *source 待匹配的字符串

TL sourceLen 待匹配字符串的长度

const T *pattern 模式串

TL 模式串长度

C++ kmp算法模板代码示例：

 
 
 

  
  
  
template < class T,class TL>   
  
  
  
inline int kmpmatch(const T *source,TL sourceLen,
const T *pattern,TL patternLen)   
  
  
  
{   
  
  
  
vector< int> next;   
  
  
  
for ( int i = 0; i <  patternLen ; i ++ )   
  
  
  
next.push_back(0);   
  
  
  
next[0] = -1;   
  
  
  
for( int i = 1 ; i <  patternLen ; i ++ )   
  
  
  
{   
  
  
  
int j = next[i - 1];   
  
  
  
while ( (pattern[i] != pattern[i + 1])&& (j >= 0))   
  
  
  
{   
  
  
  
j = next[j];   
  
  
  
}   
  
  
  
if ( pattern[i] == pattern[j + 1])   
  
  
  
{   
  
  
  
next[i] = j + 1;   
  
  
  
}   
  
  
  
else   
  
  
  
{   
  
  
  
next[i] = -1;   
  
  
  
}   
  
  
  
}   
  
  
  
int i = 0;   
  
  
  
int j = 0;   
  
  
  
while (( i <  sourceLen ) && ( j <  patternLen ))   
  
  
  
{   
  
  
  
if ( source[i] == pattern[j] )   
  
  
  
{   
  
  
  
i ++;   
  
  
  
j ++;   
  
  
  
}   
  
  
  
else if ( j == 0 )   
  
  
  
{   
  
  
  
i ++;   
  
  
  
}   
  
  
  
else   
  
  
  
{   
  
  
  
j = next[j - 1 ] + 1;   
  
  
  
}   
  
  
  
}   
  
  
  
if ( j >= patternLen )   
  
  
  
{   
  
  
  
if ( !next.empty() )   
  
  
  
next.clear();   
  
  
  
return i - patternLen ;   
  
  
  
}   
  
  
  
else   
  
  
  
{   
  
  
  
if ( !next.empty() )   
  
  
  
next.clear();   
  
  
  
return -1;   
  
  
  
}   
  
  
  
} 
 
 
 

以上就是对C++ kmp算法模板的相关介绍。