Эффективный алгоритм поиска для поиска повторяющихся строк

Question

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

Длина строки может составлять 8-20 символов, а количество строковых элементов в связанном списке составляет от 100 до 200. Современный подход, похоже, имеет проблемы сложности и эффективности. Может ли кто-нибудь предложить наиболее эффективный подход для этого?

typedef struct Map 
{ 
     int8_t *string; 
     struct Map *next; 
}map_t; 

//Algorithm to find the duplicate string pattern in link list. 

int16_t findDuplicateOids(map_t *head) 
{ 
    map_t *ptr1, *ptr2; 
    ptr1 = head; 
    /* Pick elements one by one */ 
    while(ptr1 != NULL && ptr1->next != NULL) 
    { 
    ptr2 = ptr1; 
    /* Compare the picked element with rest of the elements */ 
    while(ptr2->next != NULL) 
    { 
     /* If pattern is similar than return return error */ 
     if(!strcmp(ptr1->string , ptr2->next->string)) 
     { printf("match happened"); 
      return RESULT_ERROR; 
     } 
     else 
     { 
      ptr2 = ptr2->next; 
     } 
    } 
    ptr1 = ptr1->next; 
    } 
    return RESULT_SUCCESS; 
} 

Answer 1

Если вы хотите улучшить временную сложность вашего алгоритма, вы можете:

1. Сортировать строки в лексикографическом порядке. Затем вам нужно проверить только пары последовательных строк. Этот подход имеет сложность времени O(n log n) + O(n) = O(n log n).

2. Использование хэш-таблицы. Это решение имеет среднюю шкалу сложности O(n).

3. Используйте trie. Опять же, O(n).

Answer 2

вы можете улучшить свою сложность, используя следующие steps-

1. Используйте суффикс массив для сортировки строки в лексикографическом порядке в сложности O (NlogN).

2. Сравнить соседние строки. Общее количество сравнений, уменьшенных до n. Сложность этого шага - O (n).

   Таким образом, полная сложность O (nlogn) + O (n) = o (nlogn).