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 ---------- */

// 這個算法 也研究了很久了。對于他的原理 我早已經清楚，但是快速的寫出他還是不是那么順利。也是因為我寫的程序太少了吧 呵呵。 理解中記憶。 嗯 不能死記硬背啊 呵呵。