查找重复字符串的高效搜索算法

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. 使用特里。再次，O(n)。