#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <math.h>
#define tonum(c) (c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a' + 26)

int rabin_kapr_matcer(char *Text, char *Pattern, int d, int q) {
    int n = strlen(Text);
    int m = strlen(Pattern);
    int h = (int) pow(d, m - 1) % q;
    int p = 0;
    int t = 0;
    int found = 0;


    int i = 0;
    int j = 0;
    int s = 0;

    //предварительная обработка
    for (int i = 1; i < m; i++){
        p = (d * p + tonum(Pattern[i])) % q;
        t = (d * t + tonum(Text[i])) % q;
    }

    //Проверка
    for (int i = 0; i <= n; i++) {
        if (p == t) {
            found = 1;
            for (j = 0; j < m; j++) {
                if (Pattern[j] != Text[i + j]) {
                    found = 0;
                    break;
                }
            }
            if (found)
                return i + 1;
        }
        else {
            t = (d*(t - ((tonum(Text[i])*h) % q)) + tonum(Text[i + m])) % q;
        }

    }

    return -1;
}


int main() {

    int find;
    int d = 1, q = 1;
    char *T = "Одно из простейших практических применений алгоритма Рабина — Карпа состоит в определении плагиата. Скажем, например, что студент пишет работу по Моби Дику. Коварный профессор находит различные исходные материалы по Моби Дику и автоматически извлекает список предложений в этих материалах.";
    char *P = "Моби";

    find = rabin_kapr_matcer(T, P, d, q);
    if (find)
        printf("%d\n", find);
    else
        printf("=(((");

    return 0;
}