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

　　C++编程语言 固然 性能 壮大， 利用 模式灵便，然而在实际编程中同样会浮现各种各样的 舛误 。在这里我们将会为大家 详尽介绍一下有关C++指针漂移的解决 步骤， 盼望本文介绍的内容 可以协助大家解决问题 。

　　近期我们在工作中碰到一个奇怪的问题，最终确定是多继承引起的C++指针漂移，跟C++对象模型有关 。示意如下：

　　class A {...};  class B{...};  class AB : public B, public A {...}  ...  AB *pab = new AB();  A* pa = (A*)pab;  B* pb = (B*)pab; 这时候你发现pa和pb的值是不一样的！它们中有一个跟pab是相等的，而另外一个产生了偏移 。假如把AB的申明中A和B的顺序调换一下，则产生偏移的指针也会变为另外一个 。

　　为了确定这是编译器做了转换的缘故，利用void指针愚弄编译器：

　　void *pv = (void*)pab;  pa = (A*)pv; 这时候pa的值倒是跟pab相等了，然而指向了 舛误的地方 。从pab到pa的转换，依赖于路径的 取舍，让人不是很 释怀 。还不晓得把指针放入容器中再 存入来，会不会出错 。固然，上面 使用了强制类型转换，在良好的程序中应该幸免 。假如惟独隐式转换， 可以得到正确的 后果：

　　std::vector<A*> v;  //implicit type conversion  v.insert(v.begin(), pab);  void *pv = v[0];  pa = (A*)pv; 以下程序 使用Cygwin/g++b编译通过：

　　#include <stdio.h> #include <vector> class A   {  public:  int a;  };  class B   {  public:  int b;  };  class AB : public B, public A   {  public:  int ab;  };  int main(int argc, char **argv)  {  AB *pab = new AB();  pab->ab = 1;  pab->b = 2;  pab->a = 3;  A* pa = (A*)pab;  B* pb = (B*)pab;  printf( "AB: %p\n" \  " A: %p\n" \  " B: %p\n",  pab, pa, pb);  std::vector<A*> v;  //implicit type conversion  v.insert(v.begin(), pab);  void *pv = v[0];  pa = (A*)pv;  printf("pv is %p\npa is %p\npab %s pv\n", pv, pa, (pab == pv) ? "==" : "!=");  printf("A.a is %d\n", pa->a);  //forced type conversion  pv = (void*)pab;  pa = (A*)pv;  printf("Now A.a is %d\n", pa->a);  } 运行 后果：

　　AB: 0x6b01f0   A: 0x6b01f4   B: 0x6b01f0   pv is 0x6b01f4   pa　　C++编程语言中的模板 利用是一个 比较复杂的 利用技术，我们今日就先从C++ kmp算法模板的 根本 利用开始学习，从而加深我们对这方面 常识的 意识程度，容易 将来的 利用， 普及编程效率 。

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

　　#include < vector>   using namespace std;

　　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;   }   }

is 0x6b01f4   pab != pv   A.a is 3   Now A.a is 2