/* License: AGPLv3 or later. https://www.gnu.org/licenses/licenses.html
 * 
 * Exercise 6 - Karp-Rabin String Search (Week 7)
 * Name: Manish
 * Student Login: *****
 * 
 * Compile as:
 * $ gcc -std=c11 -Wall -o ex6 ex6.c
 * 
 * NOTE: There is error that using some small no. like 500 give incorrect (incomplete) results. Still not figured out why.
 */ 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char t[5001];
char s[11];
int t_len = 0;
int s_len = 0;
unsigned long prime = 5;
unsigned long mod = 18446744073709551557UL; // prime < 2^64
unsigned long precomputed_prime_exponent = 1;

int main(void)
{
    printf("Enter file name: ");
    char filename[257];
    // Assuming filename/file path won't be longer than 256 characters
    scanf("%256s", filename);

    FILE* file = fopen(filename, "r");
    if (!file)
    {
        perror(filename);
        exit(EXIT_FAILURE);
    }

    fscanf(file, "%5000s %10s", t, s);
    t_len = strlen(t);
    s_len = strlen(s);

    unsigned long t_hash = t[0]%5;
    unsigned long s_hash = s[0]%5;

    for (int i=1; i < s_len; i++)
    {
        precomputed_prime_exponent = (precomputed_prime_exponent*prime)%mod;
        t_hash = (((prime*t_hash)%mod) + (t[i]%5))%mod;
        s_hash = (((prime*s_hash)%mod)+ (s[i]%5))%mod;
    }

    for (int i=0; i < t_len-s_len; i++)
    {
        if (t_hash == s_hash)
        {
            if (strncmp(&t[i], s, s_len) == 0)
                printf("%d ", i);
        }
        // %5 for characters and %mod every + & * part of equation
        t_hash = (
            (((prime*
            (t_hash -
            ((precomputed_prime_exponent*(t[i]%5))%mod)
            ))%mod) +
            (t[i+s_len]%5))
            %mod);
    }
    printf("\n");

    fclose(file);

    return 0;
}