基础KMP， 要注意一次查找完成后，到下一可查找处继续匹配，这样才能保证得到最终个数。 

code:

#include<cstdio>

#include<cstring>

char substr[

10001] ;

char str[

1000001] ;

int next[

10001] ;

int sublen, len, ans ;

void get_next(){

    next[

1] = 

0 ;

    

int j = 

0 ;

    

for(

int i=

2; i<=sublen; i++){

        

while(j>

0&&substr[j+

1]!=substr[i])

            j = next[j] ;

        

if(substr[j+

1]==substr[i])  j ++ ;

        next[i] = j ;

    }

}

void kmp(){

    

int j = 

0 ;

    

for(

int i=

1; i<=len; i++){

        

while(j>

0&&substr[j+

1]!=str[i])

            j = next[j] ;

        

if(substr[j+

1]==str[i]) j ++ ;

        

if(j==sublen){

            ans ++ ;

            j = next[j] ;   

//

一次查找完成后，到下一可查找处继续匹配

        }

    }

    printf(

"

%d\n

", ans) ;

}

int main(){

    

int t ;

    scanf(

"

%d

", &t) ;

    

while(t--){

        scanf(

"

%s

", substr+

1) ;

        scanf(

"

%s

", str+

1) ;

        ans = 

0 ;

        sublen = strlen(substr+

1) ;

        len = strlen(str+

1) ;

        get_next() ;

        kmp() ;

    }

    

return 

0 ;

}