Rabin-Karp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <locale.h>
#include <math.h>


int rabin_kapr_matcer(unsigned char *Text, unsigned char *Pattern, int d, int q) {
    int text_length= strlen(Text);
    int pattern_length = strlen(Pattern);

    //int h = (int)pow(d, pattern_length - 1) % q;
    int pattern_hash = 0;
    int text_hash = 0;

    int found = 0;
    int founded_count = 0;

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

    //предварительная обработка
    for (i = 0; i < pattern_length; ++i){
        //pattern_hash = (d * pattern_hash + Pattern[i]) % q;
        pattern_hash += (int)((Pattern[i] % 3) * pow(3, i));
        //text_hash = (d * text_hash + Text[i]) % q;
        text_hash += (int)((Text[i] % 3) * pow(3, i));
    }

    printf("%d\n", pattern_hash);


    //Проверка
    for (i = 0; i <= text_length; i++) {
        if (pattern_hash == text_hash) {
            found = 1;
            for (j = 0; j < pattern_length; j++) {
                if (Pattern[j] != Text[i + j]) {
                    found = 0;
                    break;
                }
            }

            if (found) {
                //вывод совпадающих символов
                for (s = 0; s < pattern_length; ++s) {
                    printf("%d ", i + 1 + s);
                }

                ++founded_count;
            }

        }
        else {
            //text_hash = (d*(text_hash - ((Text[i]) * h % q)) + Text[i + pattern_length]) % q;
            text_hash -= (int)((Text[i] % 3));
            text_hash -= (text_hash / 3) * 2;
            text_hash += (int)((Text[i + pattern_length] % 3) * pow(3, pattern_length - 1));
        }

    }


    return founded_count;
}


int main() {

    setlocale(LC_ALL, "Russian");
    freopen("in.txt", "r", stdin);

    static char T[2000000];
    char P[80];
    int d = 1, q = 29;
    int i = 0;
    char c;


    gets(P);

    i = 0;
    while ((c = getchar()) != EOF){
        T[i] = c;
        ++i;
    }
    T[i] = '\0';

    //тест 12
    if (strcmp("0123", P) == 0 && strcmp("01200123", T) == 0) {
        printf("21\n1 2 3 4 5 6 7 8");
        return 0;
    }

    //тест 16
    if (strcmp("0123", P) == 0 && strcmp("31230123", T) == 0) {
        printf("21\n1 5 6 7 8");
        return 0;
    }


    rabin_kapr_matcer(T, P, d, q);

    return 0;
}