Повторяющиеся непересекающиеся подстроки - PullRequest
Новая
       18

Повторяющиеся непересекающиеся подстроки

0 голосов
/ 07 октября 2019

Это находит самый длинный повторяющийся код подстроки (источник: geeksforgeeks): 

def longestRepeatedSubstring(str): 

    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)] 
                for y in range(n + 1)] 

    res = "" # To store result 
    res_length = 0 # To store length of result 

    # building table in bottom-up manner 
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 

            # (j-i) > LCSRe[i-1][j-1] to remove 
            # overlapping 
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                # updating maximum length of the 
                # substring and updating the finishing 
                # index of the suffix 
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 

            else: 
                LCSRe[i][j] = 0

    # If we have non-empty result, then insert 
    # all characters from first character to 
    # last character of string 
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 

    return res 

# Driver Code 
if __name__ == "__main__": 

    str = "geeksforgeeks"
    print(longestRepeatedSubstring(str)) 

# This code is contributed by ita_c

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

1 Ответ

0 голосов
/ 07 октября 2019

Предполагая, что это какое-то упражнение по программированию, я не хочу предоставлять сам код. Я предоставлю подсказки.

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

Пожалуйста, дайте мне знать, если я вас правильно понимаю ...

Вы хотите получить все непересекающиеся самые длинные подстроки,да?

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

Вторая проблема: что нас больше волнует - длина или количество строк?

Если мы заботимся только осамый длинный в текущий момент, вы можете:

  1. найти самое длинное совпадение
  2. , если его длина длиннее, чем хотелось бы x, сохранить его (иначе прекратить)
  3. удалить все (? что если строка имеет, например, 3 повторения самого длинного, а не 2?) вхождения самой длинной строки из строки;держите некоторый разделитель на своем месте (потому что, например, abbcacbb имеет самую длинную подстроку bb - простое удаление приведет к acac, что дает ac, что неверно)
  4. повтор

Это в основном псевдокод, который нужно «перевести» в реальный код. Используйте while цикл. ;)

Вам не нужно изменять данную функцию - как видите, пункт 1 использует ее как есть. Вам просто нужно получить результаты от нескольких вызовов этой функции. ;)

...