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

char* search(char* txt, char* word) {
  int i = 0;
  while (true) {
    int j = 0;
    while (word[j] != '\0' && txt[i+j] != '\0' && word[j] == txt[i+j]) { j++; }
    if (word[j] == '\0') { return &txt[i]; }
    if (txt[i+j] == '\0') { return NULL; }
    i++;
  }
  return NULL;
}

int expo(int d, int n, int q) {
  if (n==0)
    return 1 ;
  else {
    int a = expo(d, n/2, q) ;
    if (n % 2 == 0)
      return (a*a) % q ;
    else
      return (a*a*d) % q ;
  }
}

int q = 683303;
int d = 256;

int convert(char* s, int m) {
  int somme = 0 ;
  for (int i = 0; i < m; i++) {    
    somme = (somme * d + (int)s[i]) % q ;
  }
  return somme ;
}

char* rabin_karp(char* txt, char* word) {
  int m = strlen(word);
  int p = expo(d, m-1, q);
  int hword = convert(word, m);
  int hs = convert(txt, m);
  int i = 0 ;
  while (true) {
    char c = txt[i+m] ;
    txt[i+m] = '\0'; // pour le strcmp
    if (hs == hword && strcmp(&txt[i], word) == 0) {
      txt[i+m] = c;
      return &txt[i]; 
    }
    txt[i+m] = c;
    if (c == '\0') { return NULL; } // fin du txt
    hs = ((hs - ((int)(txt[i])*p) % q) * d + (int)c) % q;
    i++;
  }
  return NULL;
}

void test_naif(char* txt, char* word) {
  printf("\nTest de l'algo naïf~:\n");
  char* res = search(txt,word);
  if (res != NULL) {
    printf("La chaîne suivante commence par %s : %s\n", word, res);
  }
  else {
    printf("Chaine %s non trouvée par l'algo naïf\n", word);
  }
}

void test_rk(char* txt, char* word) {
  printf("\nTest de Rabin Karp~:\n");
  char* res = rabin_karp(txt,word);
  if (res != NULL) {
    printf("La chaîne suivante commence par %s : %s\n", word, res);
  }
  else {
    printf("Chaine %s non trouvée par Rabin Karp\n", word);
  }
}

int main() {
  char txt[] = "Vive la MPI !";
  char word[] =  "MPI";
  printf("Ce test doit afficher 78559 : %d\n", convert(&txt[1],3));
  test_naif(txt, word);
  test_rk(txt, word);
}