Как я могу найти строку с одной ошибкой в ​​tr ie?

Question

Дано: Некоторые большие входные файлы, содержащие строки одинаковой длины k (обычно 99 символов), состоящие из символов A, G, T, C.

Задача: Код алгоритма в C, который будет искать строку из m> k (обычно 110) символов, так что если последние k-1 символов строки совпадают с первыми k- 1 из другого, они должны быть объединены. Например, если я ищу строку AGTCC в наборе {AGTC, GTCC}, это даст положительный результат.

Алгоритм должен также вывести наилучший точный префикс в случае, если искомая строка отсутствует в list.

Кроме того, алгоритм должен также давать положительный вывод, если искомая строка отличается от одной существующей строки на один символ.

Самый умный способ, который я мог придумать, был организовать этот огромный список в четвертичном (?) дереве: каждый узел содержит массив из 4 указателей на другие узлы, и они изначально равны NULL. Когда символ добавляется, я изменяю массив следующим образом: если вход является AI, выделяем 0-ую позицию массива новому узлу с массивом NULL, если это C первый, если G второе, если T третье.

Например, изначально root равно {NULL, NULL, NULL, NULL}. Если первый символ, который я добавляю, это C, я создаю новый узел N с массивом NULL, а затем меняю root на {NULL, N, NULL, NULL}. Я объяснил это своему профессору, и он заявил, что это фактически используемая структура данных, называемая tr ie.

. Я могу выполнить поиск и найти лучшую подстроку за O (m) времени с этой структурой, просто следуя по дереву, пока я не достигну узла {NULL, NULL, NULL, NULL}.

Лучший способ, который я мог бы придумать, чтобы выполнить поиск с несовпадением, - это найти каждое возможное несоответствие в лучшей подстроке и затем выполнить снова весь поиск, что приводит к сложности O (4m ^ 2). Это неплохо, но я бы хотел сделать это линейным.

Есть ли какой-нибудь сумасшедший алгоритм, который может выполнять очень эффективный поиск с одним несоответствием в tr ie? Вот что у меня есть:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define k 99
#define m 110 
#define L 10000000 //Check variable in case the input file isn't properly formatted with EOF
typedef struct tree{
  struct tree* base[4];
} node;
int hash(char r){
  if (r=='A') return 0;
  if (r=='C') return 1;
  if (r=='G') return 2;
  if (r=='T'||r=='N') return 3; //Ignore the N bit
  return -1;
}

char invhash(int x){ 
  if (x==0) return 'A';
  if (x==1) return 'C';
  if (x==2) return 'G';
  if (x==3) return 'T';
  return -1;
}

node* newnode(){
  node* new=malloc(sizeof(node));
  for (int i=0; i<4; i++) {
    new->base[i]=malloc(sizeof(node));
    new->base[i]=NULL;
  }
  return new;
}

node* trovak(char* target, node* s, int level){ //Searches a string of length k and outputs a pointer to its leaf if it finds it and NULL otherwise
  if (level==k) return s;
  int h=hash(target[level]);
  if (s->base[h]==NULL){
    return NULL;
  }
  return trovak(target, s->base[h], level+1);
}


void newtree(node* s, char* kmero){ //Adds the string kmero to the tree s
  int h;
  for (int l=0; l<k; l++){
    h=hash(kmero[l]);
    if (s->base[h]==NULL){
      s->base[h]=newnode();
    }
    s=s->base[h];
  }
  return;
}


int trova(char* target, node* s,int level){ //This searches the whole target string in the tree
  if (level==m) return m;
  int h=hash(target[level]);
  if (s->base[h]==NULL){
    printf("There isn't %c (character number %d)\n", invhash(h), level);
    return level;
  }
  return trova(target, s->base[h], level+1);
}

int main(){
  FILE* file=fopen("KAPPA105.txt", "r"); //List of strings file
  FILE* ricerca=fopen("ricerca.txt", "r"); //Target string file
  node* s=newnode(); //Root of tree
  int level=0; //Same as L, don't worry about it
  char* target=malloc(m); //Actual target string
  char* kmero=malloc(k); 
  node* leaf=malloc(sizeof(node)); //Used to build the tree, din't worry about it
  node* linksucc=malloc(sizeof(node)); //Same
  target=fgets(target, m+1, ricerca);
  char* SUCC_KMER=malloc(k); 
  //Creating the tree
  do{
    kmero=fgets(kmero, k+1, file);
    newtree(s, kmero);
    level++;
  } while (fgetc(file)!=EOF&&level<L);
  rewind(file);
  level=0;
  //The tree has always height k, so I attach all the leaves in order to do the concatenation thing
  do{
    leaf=s;
    kmero=fgets(kmero, k+1, file);
    for (int l=0; l<k; l++) leaf=leaf->base[hash(kmero[l])]; 
    strncpy(SUCC_KMER, kmero+1, k-1);
    for (int i=0; i<4; i++){
      SUCC_KMER[k-1]=invhash(i); 
      linksucc=trovak(SUCC_KMER, s, 0); 
      leaf->base[i]=linksucc; /
    }
    level++;
  } while (fgetc(file)!=EOF&&level<L);

  ////////////////////////////////////////////////////////////
  //Formatting thing
  for (int i=0; i<m; i++) putchar(target[i]);
  putchar('\n');
  for (int i=0; i<m; i++) putchar('-');
  putchar('\n');
  int pos=trova(target, s, 0); //Perform the search
  if (pos==m){
    printf("The string is present in the list.\n");
    return 2;
  }
  else{
    printf("Best prefix (%d characters):\n", pos);
    for (int i=0; i<pos; i++) putchar(target[i]);
    putchar('\n');
    //What if there is a single mismatch?????
  }
  return 0;
}