kmp变形 如何判断第i个字符是否匹配函数 hdu 4749

const int Max_N = 100005 ;
int sumt[Max_N][26]  , sump[Max_N][26] ; // sum[i][j]表示从第1位到第i位，有sum[i][j] 个j
int TT[Max_N] , PP[Max_N] , next[Max_N] ;
int n , m , k ;
// 每次匹配时 是
//   (1 ,2 ,... , j)
// 与(i-j + 1 , ... , i)进行匹配
bool  ok1(int i, int j){
    int sma1= 0 , equ1 = 0 ,  sma2 = 0 , equ2 = 0 ;
    int h ;
    for(h = 1 ; h <= k ; h++){
        if(h < PP[i])
            sma1 += sump[i][h] - sump[i - j][h] ;
        else if(h == PP[i])
            equ1 += sump[i][h] - sump[i - j][h] ;
        if(h < PP[j])
            sma2 += sump[j][h] ;
        else if(h == PP[j])
            equ2 += sump[j][h] ;
    }
    return (sma1 == sma2) && (equ1 == equ2) ;
}
void get_next(){
    int i , k = 0 ;
    next[1] = 0 ;
    for( i = 2 ; i<= m ; i++){
        while(k > 0 && !ok1(i , k + 1))
            k = next[k] ;
        if(ok1(i, k + 1))
            k ++ ;
        next[i] = k ;
    }
}
bool ok2(int i , int j){
    int sma1 = 0 , equ1 = 0 ,  sma2 = 0 , equ2 = 0 ;
    int h ;
    for(h = 1 ; h <= k ; h++){
        if(h < TT[i])
            sma1 += sumt[i][h] - sumt[i - j][h] ;
        else if(h == TT[i])
            equ1 += sumt[i][h] - sumt[i - j][h] ;
        if(h < PP[j])
            sma2 += sump[j][h] ;
        else if(h == PP[j])
            equ2 += sump[j][h] ;
    }
    return (sma1 == sma2) && (equ1 == equ2) ;
}
int kmp(){
    int i , k = 0 ;
    int cnt = 0 ;
    for(i = 1 ; i<= n ; i++){
        while(k > 0 && !ok2(i , k + 1))
            k = next[k] ;
        if(ok2(i , k + 1))
            k ++ ;
        if(k == m){
            cnt ++ ;
            k = 0 ; // 特殊处理， 字串不相交
        }
    }
    return cnt ;
}
int main(){
    while(scanf("%d%d%d" , &n ,&m ,&k) != EOF){
        int i , j ;
        memset(sumt , 0 , sizeof(sumt)) ;
        memset(sump , 0 , sizeof(sump)) ;
        for(i = 1 ; i<= n ; i++){
             scanf("%d" , &TT[i]) ;
            for(j = 1 ; j<= k ; j++)  sumt[i][j] = sumt[i - 1][j] ;
                sumt[i][TT[i]] ++ ;
        }
        for(i = 1 ; i<= m ; i++){
            scanf("%d" , &PP[i]) ;
            for(j = 1 ; j <= k ; j++) sump[i][j] = sump[i - 1][j] ;
            sump[i][PP[i]] ++ ;
        }
        get_next() ;
        printf("%d\n" , kmp()) ;
    }
    return 0 ;
}