POJ 3461 裸KMP

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        poj3461.cpp 
*  Create Date: 2013-11-27 09:38:47 
*  Descripton:  kmp  
*/  
  
#include   
#include   
  
const int MAXN = 1000010;  
char T[MAXN], P[10010];  
int f[10010];  
  
void getVal(int l) {  
    int i = 0, j = -1;  
    f[0] = -1;  
    while (i < l) {  
        if (j == -1 || P[i] == P[j]) {  
            i++;  
            j++;  
            f[i] = j;  
//          if (P[i] != P[j])  
//              f[i] = j;  
//          else  
//              f[i] = f[j];  
        }  
        else  
            j = f[j];  
    }  
}  
int KMP() {  
    int lent = strlen(T), lenp = strlen(P);  
    getVal(lenp);   // get next  
    int i = 0, j = 0, ans = 0;  
    while (i < lent) {  
        if (j == -1 || T[i] == P[j]) {  
            i++;  
            j++;  
        } else   
            j = f[j];  
        if (j == lenp) {  
            ans++;  
            j = f[j];  
        }  
    }  
    return ans;  
}  
  
int main() {  
    int t;  
    scanf("%d", &t);  
    while (t--) {  
        scanf("%s%s", P, T);  
        printf("%d\n", KMP());  
    }  
    return 0;  
}