KMP

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;

// Implement the failure function
void failure_function(const char* pat, int failure[]){
    string str = pat;
    for(int i = 1, j = failure[0] = -1; i<str.length();++i){
        while(j >= 0 && str[j+1] != str[i]){
            j = failure[j];
        }
        if(str[j+1] == str[i]){j++;}
        failure[i] = j;
    }
    for(int i=0;i<str.length();++i){cout << failure[i] << ' ';}
    cout << '\n';
}

// Return the position of the first occurrence of pat in s
int pmatch(const char *str, const char *pat,int failure[]){
    string a = str, b = pat;
    if(a.length() < b.length())return -1;
    for(int i=0, j=-1;i<a.length();i++){
        while (j >= 0 && b[j+1] != a[i]){
            j = failure[j];
        }
        if(b[j+1] == a[i])j++;

        // pattern matched
        if(j == b.length() - 1){
            int pos = i - b.length() + 1;
            return pos;
        }
    }
    return -1;
}

// Do not modify the main function
int main(){
    char pat[100], s[500]; int f[100];
    int i, pos, first_char, count;
    scanf("%s",s); scanf("%s", pat);
    failure_function(s, f);
    failure_function(pat,f);
    pos = 0; count = 0;

    do{
        first_char = pmatch(s + pos, pat, f);
        if(first_char != -1) {
            count++;
            pos = pos + first_char + 1;
        }
        else{break;}
    }while(1);
    printf("%d\n",count);
    return 0;
}
/*
abcabcabcaabcdabcde
abc
*/