KMP

/*
    Task    : KMP
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 30 January 2023 [19:56]
*/
#include<bits/stdc++.h>
using namespace std;
char a[1010],b[1010];
int prep[1010];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> a+1 >> b+1;
    int lena = strlen(a+1),lenb = strlen(b+1);
    int j=0;
    for(int i=2;i<=lenb;i++){
        while(j>0 && b[j+1] != b[i])    j = prep[j];
        if(b[j+1] == b[i])  j++;
        prep[i] = j;
    }
    j = 0;
    for(int i=1;i<=lena;i++){
        while(j>0 && b[j+1] != a[i])    j = prep[j];
        if(b[j+1] == a[i])  j++;
        if(j == lenb){
            cout << "founded\n";
            return 0;
        }
    }
    cout << "not found\n";
    return 0;
}