< 返回技术文档列表

C++中怎么实现一个 kmp算法

发布时间:2021-09-01 02:18:17⊙投诉举报

本篇文章给大家分享的是有关C++中怎么实现一个 kmp算法,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

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

const T *source 待匹配的字符串

TL sourceLen 待匹配字符串的长度

const T *pattern 模式串

TL 模式串长度

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

  1. template < class T,class TL>   

  2. inline int kmpmatch(const T *source,TL sourceLen,
    const T *pattern,TL patternLen)   

  3. {   

  4. vector< int> next;   

  5. for ( int i = 0; i <  patternLen ; i ++ )   

  6. next.push_back(0);   

  7. next[0] = -1;   

  8. for( int i = 1 ; i <  patternLen ; i ++ )   

  9. {   

  10. int j = next[i - 1];   

  11. while ( (pattern[i] != pattern[i + 1])&& (j >= 0))   

  12. {   

  13. j = next[j];   

  14. }   

  15. if ( pattern[i] == pattern[j + 1])   

  16. {   

  17. next[i] = j + 1;   

  18. }   

  19. else   

  20. {   

  21. next[i] = -1;   

  22. }   

  23. }   

  24. int i = 0;   

  25. int j = 0;   

  26. while (( i <  sourceLen ) && ( j <  patternLen ))   

  27. {   

  28. if ( source[i] == pattern[j] )   

  29. {   

  30. i ++;   

  31. j ++;   

  32. }   

  33. else if ( j == 0 )   

  34. {   

  35. i ++;   

  36. }   

  37. else   

  38. {   

  39. j = next[j - 1 ] + 1;   

  40. }   

  41. }   

  42. if ( j >= patternLen )   

  43. {   

  44. if ( !next.empty() )   

  45. next.clear();   

  46. return i - patternLen ;   

  47. }   

  48. else   

  49. {   

  50. if ( !next.empty() )   

  51. next.clear();   

  52. return -1;   

  53. }   

以上就是C++中怎么实现一个 kmp算法,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注血鸟云行业资讯频道。


/template/Home/Zkeys/PC/Static