C++中怎么實現一個 kmp算法

本篇文章給大家分享的是有關C++中怎么實現一個 kmp算法，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

C++ kmp算法模板參數說明

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算法，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。