poj 3167 kmp 经典

就是一个kmp的变形，关键是怎么计算next数组，对于该题就是：找出最长的前缀序列，使得该序列的偏序关系
（也有acmer称为串排名）与相应的后缀序列的偏序关系相同。顺着这个思路，你可能会想怎样快速比较两个序
列的偏序关系。我想了好久，没有头绪。。。 注意到1<=S<=25这个条件，也就是说序列中的元素是有限制的，这样我们可以通过统计序列中元素出现到次数来比较偏序关系。这时有一个结论要用到：

两个序列的偏序关系相同当且仅当这两个序列的每个位置上的元素前面等于它的元素个数和小于它的元素个数都相等

#include <stdio.h>
#include <string.h>

#define MAX_COW_NUMBER 100001
#define MAX_PTN_NUMBER 25001

int N, K, S;
int cowline[MAX_COW_NUMBER];
int pattern[MAX_PTN_NUMBER];
int next[MAX_PTN_NUMBER];

int res[MAX_COW_NUMBER];
int resNum;

// p[i][j] indicates the number of j in the front i numbers
int array1[MAX_PTN_NUMBER][26];
int array2[MAX_COW_NUMBER][26];

void preprocess() {
    int i, j;
    for( i=1; i<=S; i++ ) {
    array1[0][i] = array2[0][i] = 0;
    }
    for( i=1; i<=K; i++ ) {
    for( j=1; j<=S; j++ ) {
        array1[i][j] = array1[i-1][j] + (j==pattern[i]);
    }
    }
    for( i=1; i<=N; i++ ) {
    for( j=1; j<=S; j++ ) {
        array2[i][j] = array2[i-1][j] + (j==cowline[i]);
    }
    }
}

int isMatch(int* p, int (*ary1)[26], int pk, int ps, int* t, int (*ary2)[26], int tk, int ts) {
    int i;
    // compute the number of numbers which are less than p[pk]
    int pLessNumber = 0, tLessNumber = 0, pEqualNumber = 0, tEqualNumber = 0;
    for( i=1; i<p[pk]; i++ )
    pLessNumber += ary1[pk-1][i] - ary1[pk-ps-1][i];
    for( i=1; i<t[tk]; i++ )
    tLessNumber += ary2[tk-1][i] - ary2[tk-ts-1][i];
    pEqualNumber = ary1[pk-1][p[pk]] - ary1[pk-ps-1][p[pk]];
    tEqualNumber = ary2[tk-1][t[tk]] - ary2[tk-ts-1][t[tk]];

    return pLessNumber == tLessNumber && pEqualNumber == tEqualNumber;
}

void compute_prefix_function() {
    int i;
    int k;
    next[1] = 0;
    next[2] = 1;
    k = 1;
    for( i=3; i<=K; i++ ) {
    int match = isMatch(pattern, array1, k+1, k, pattern, array1, i, k);
    while( k>0 && !match) { // compare pattern[k+1] with pattern[i]
        k = next[k];
        match = isMatch(pattern, array1, k+1, k, pattern, array1, i, k);
    }
    if( match )
        k++;
    next[i] = k;
    }
}

void Knuth_Morris_Pratt() {
    int i;
    int k = 0;
    for( i=1; i<=N; i++ ) {
    int match = isMatch( pattern, array1, k+1, k, cowline, array2, i, k);
    while( k>0 && !match) {
        k = next[k];
        match = isMatch( pattern, array1, k+1, k, cowline, array2, i, k);
    }
    if( match ) {

        k++;
    }


    if( k == K ) {
//        printf("%d", i-K+1);
        res[resNum++] = i-K+1;
        k = next[k];
    }
    }
    printf("%d\n", resNum);
    for( i=0; i<resNum; i++)
    printf("%d\n", res[i]);

}

int main() {
    int i;
    while( EOF != scanf("%d %d %d", &N, &K, &S) ) {
    for( i=1; i<=N; i++)
        scanf("%d", &cowline[i]);
    for( i=1; i<=K; i++ )
        scanf("%d", &pattern[i]);

    preprocess();
    compute_prefix_function();
    resNum = 0;
    Knuth_Morris_Pratt();
    }

    return 0;
}