template<typename T>
void prefix(T* p, int m, int* next)
{
int i, j;
i = 0;
j = next[0] = -1;
while (i < m) {
while (j > -1 && p[i] != p[j])
j = next[j];
i++;
j++;
if (p[i] == p[j])
next[i] = next[j];
else
next[i] = j;
}
}
/* ---------- end of function prefix ---------- */
/*****************************************************************************
* Function : KMP *
* T *t : The string need be matching *
* int n : The length of the string *
* T *p : The sub string to matching *
* int m : The length of the p *
* int *out : An array mark the string match where ( max length is m - n ) *
*****************************************************************************/
template<typename T>
int KMP(T* t, int n, T* p, int m, int* out)
{
int c = 0;
int i, j, next[m];
prefix(p, m, next);
i = 0;
j = 0;
while(i < n)
{
while( j > -1 && p[j] != t[i])
j = next[j];
i++; j++;
if( j >= m )
{
out[c++] = i - m;
j = next[j];
}
}
return c;
}
/* ---------- end of function KMP ---------- */
// 这个算法 也研究了很久了。对于他的原理 我早已经清楚，但是快速的写出他还是不是那么顺利。也是因为我写的程序太少了吧 呵呵。 理解中记忆。 嗯 不能死记硬背啊 呵呵。