KMP

一对相等的真前缀与真后缀的个数（nxt数组）

void get_nxt(char s[], int len)//前缀函数
{
    nxt[1] = 0;
    for (re i = 2, j = 0; i <= len; i++)
    {
        while (j && s[i] != s[j + 1]) j = nxt[j];
        if (s[i] == s[j + 1]) j++;
        nxt[i] = j;
    }
}
void match(char s[], int lens, char t[], int lent)//s在t中出现的次数
{
    for (re i = 1; j = 0; i <= lent; i++)
    {
        while (j && (t[i] != s[j + 1] || j == lens)) j = nxt[j];
        if (t[i] == s[j + 1]) j++;
        if (j == lens)
        {
            ++ans;
            j = nxt[j];
            //return i - j + 1;//s在t中出现的第一个位置
        }
    }
}

原文地址：http://www.cnblogs.com/sandom/p/16833395.html