void getnext(const char P[], int next[])
{
    int q, k;
    int m = strlen(P); // 模板字符串的长度
    next[0] = 0;
    for(q = 1, k = 0; q < m; ++q) { // 从第二个字符开始，依次计算每个字符对应的next值
        while(k > 0 && P[q] != P[k]) {
            k = next[k-1];
        }
        if(P[q] == P[k]) {
            k++;
        }
        next[q] = k;
    }
}

int kmp(const char T[], const char P[], int next[]) 
{
    int n, m;
    int i, q;
    n = strlen(T);
    m = strlen(P);
    getnext(P, next); // 计算next数组
    for(i = 0, q = 0; i < n; ++i) {
        while(q > 0 && P[q] != T[i]) {
            q = next[q-1];
        }
        if(P[q] == T[i]) q++;
        if(q == m) {
            // 输出找到的位置
            cout << (i-m+1) << endl;
        }
    }
}