Как найти длину самой короткой уникальной подстроки и количество вхождений всех уникальных подстрок одинаковой длины в данной строке

Question

Проблема состоит в том, чтобы найти длину самой короткой уникальной подстроки и количество уникальной подстроки той же длины, встречающейся в строке. Например, «aat cc» будет иметь «t» в качестве уникальной подстроки самой короткой длины, а длина равна 1, поэтому выходные данные будут 1,1. Другой пример - «aa cc», здесь вывод будет равен 2,3, так как строки aa, a c, cc

Я пытался решить эту проблему, но мог придумать только грубую силу решение, которое должно l oop по всем возможным подстрокам. Превышен лимит времени.

Я гуглил его и нашел некоторые ссылки на суффиксный массив, но не совсем ясно об этом. Итак, каково оптимальное решение для этой проблемы?

РЕДАКТИРОВАТЬ : Забыл упомянуть ключевое требование решения, которое требовалось для этой проблемы, а именно НЕ используйте любые библиотечные функции, кроме функций ввода и вывода, для чтения и записи со стандартного ввода и на стандартный вывод и соответственно на него.

РЕДАКТИРОВАНИЕ : я нашел другое решение, используя tr ie структура данных.

Pseudocode:
for i from 1 to length(string) do
  for j from 0 to length(string)-1 do
     1. create a substring of length i from jth character
     2. if checkIfSeen(substring) then count-- else count++ 
  close inner for loop
  if count >= 1 then break
close outer for loop
print i(the length of the unique substring), count (no. of such substrings)

checkIfSeen(Substring) will use a trie data structure which 
will run O(log l) where l is the average length of the prefixes.

Сложность по времени этого алгоритма будет O (n ^ 2 log l), где, если средняя длина префиксов равна n / 2, тогда сложность по времени будет O (n ^ 2 журнал n). Пожалуйста, укажите на ошибки, если есть, а также, если возможно, на то, чтобы улучшить время выполнения.

Answer 1

Извините, но имейте в виду, что мой ответ основан на программе, которую я написал с помощью Python, но может быть применен к любому языку программирования:)

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

1: начать грубую силу с наименьшей длины подстроки, которая равна 1.

2: после цикла по строке с длина подстроки 1 (данные будут выглядеть примерно так: {"a": 2, "t": 1, "c": 2} для "aat cc"), проверьте, появилась ли какая-либо подстрока только один раз. Если это так, подсчитайте вхождение, пройдя по словарю (в приведенном вами примере «t» появилось только один раз, поэтому вхождение равно 1).

3: после подсчета вхождения разбейте l oop чтобы не тратить время на подсчет остальных больших подстрок.

4: on 2 :, если уникальная подстрока не была найдена, сбросить словарь и попробовать большую подстроку ( данные могут быть чем-то вроде {"aa": 1, "a c": 1, "cc": 1 для "aa cc"}). В конце концов, уникальная подстрока будет найдена независимо от того, что (например, в строке "aaaaa" уникальная подстрока - "aaaaa" с данными {"aaaaa": 1})

Здесь реализация в Python:

def countString(string):
    for i in range(1, len(string)+1): #start the brute force from string length 1

        dictionary = {}
        for j in range(len(string)-i+1):  #check every combination.

            #count the substring occurrences
            try:
                dictionary[string[j:j+i]] += 1
            except:
                dictionary[string[j:j+i]] = 1

        isUnique = False #loop stops if isUnique is True
        occurrence= 0
        for key in dictionary: #iterate through the dictionary
            if dictionary[key] == 1: #check if any substring is unique
                #if found, get ready to escape from the loop and increase the occurrence
                isUnique = True
                occurrence+=1

        if isUnique: 
            return (i, occurrence)

print(countString("aacc")) #prints (2,3)
print(countString("aatcc")) #prints (1,1)

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