【KMP】ZOJ 3587

kmpの性質を利用して,kmpは前i個が主列に現れる回数(カバー可能)を探し出すことができ,同様に後j個が主列に現れる回数を探し出すことができ,逆kmpだけでよい==具体的には2回の前処理順方向&逆方向を実現し,num 1とnum 2配列を記録する
だから複雑度は線形時間.....kmpを理解するのがポイント!

#define N 100005
char s[N],t[N];
int next1[N],next2[N];
int num1[N],num2[N];//  i          i   
int l1,l2;
void gao1(){
    int i,j=-1;
    next1[0] = -1;
    for(i=1;i=0 && t[i]!=t[j+1]){
            j = next1[j];
        }
        if(t[i]==t[j+1])j++;
        next1[i] = j;
    }
}
void gao2(){
    int i,j = l2;
    next2[l2-1] = l2;
    for(i=l2-2;i>=0;i--){
        while(j=0;i--){
        if(num1[i]){
            if(next1[i]!=-1){
                num1[next1[i]]+=num1[i];
            }
        }
    }
    ///
    j = l2;
    for(i=l1-1;i>=0;){
        if(s[i]==t[j-1]){
            num2[j-1]++;
            i--,j--;
        } else {
            if(j!=l2){
                j = next2[j];
            } else i--;
        }
    }
    for(i=0;i