Rabin Karp

/*
    Task    : _example
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 30 January 2023 [21:47]
*/
#include<bits/stdc++.h>
using namespace std;
char a[1010],b[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 hasha = 0,hashb = 0;
    for(int i=1;i<=lenb;i++){
        hasha = ((hasha * 29) + (a[i] - 'a')) % 1000003;
        hashb = ((hashb * 29) + (b[i] - 'a')) % 1000003;
    }
    int num = 1;
    for(int i=1;i<=lenb-1;i++)
        num = (num * 29) % 1000003;
    for(int i=1;i<=lena-lenb;i++){
        if(hasha == hashb){
            bool ok = true;
            for(int j=1;j<=lenb;j++){
                if(a[i+j-1] != b[j]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                cout << "founded\n";
                return 0;
            }
        }
        hasha -= ((a[i] - 'a') * num) % 1000003;
        hasha += 1000003;
        hasha %= 1000003;

        hasha = ((hasha * 29) + (a[i+lenb] - 'a')) % 1000003;
    }
    cout << "not found\n";
    return 0;
}