Each time we find a match, increase the global counter by 1.

For KMP, algorithm, you may refer to the following links which have nice explanations.

1. ;
2. , with a well-commented C code.

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 vector
        
          kmpProcess(string t) { 8     int n = t.length(); 9     vector
         
           lps(n, 0);10     for (int i = 1, len = 0; i < n; ) {11         if (t[i] == t[len])12             lps[i++] = ++len;13         else if (len) len = lps[len - 1];14         else lps[i++] = 0;15     }16     return lps;17 }18 19 int kmp(string s, string t) {20     int m = s.length(), n = t.length(), cnts = 0;21     vector
          
            lps = kmpProcess(t);22 for (int i = 0, j = 0; i < m; ) {23 if (s[i] == t[j]) {24 i++;25 j++;26 }27 if (j == n) cnts++;28 if (i < m && s[i] != t[j]) {29 if (j) j = lps[j - 1];30 else i++;31 }32 }33 return cnts;34 }35 36 int main(void) {37 int cases;38 scanf("%d", &cases);39 for (int i = 0; i < cases; i++) {40 string s, t;41 cin >> t;42 cin >> s;43 printf("%d\n", kmp(s, t));44 }45 return 0;46 }