Рубрики

Самая длинная повторяющаяся и не перекрывающаяся подстрока

По заданной строке str найдите в ней самую длинную повторяющуюся неперекрывающуюся подстроку. Другими словами, найдите 2 одинаковые подстроки максимальной длины, которые не перекрываются. Если существует более одной такой подстроки, верните любую из них.

Примеры:

Input : str = "geeksforgeeks"
Output : geeks

Input : str = "aab"
Output : a

Input : str = "aabaabaaba"
Output : aaba

Input : str = "aaaaaaaaaaa"
Output : aaaaa

Input : str = "banana"
Output : an 
         or na

Наивное решение : Проблема может быть легко решена путем взятия всех возможных подстрок и для всех подстрок проверьте его на оставшуюся (не перекрывающуюся) строку, если существует идентичная подстрока. Всего имеется O (n 2 ) подстрок, и проверка их по оставшейся строке займет O (n) времени. Таким образом, общая временная сложность вышеуказанного решения составляет O (n 3 ).

Динамическое программирование . Эту проблему можно решить за O (n 2 ) с помощью динамического программирования. Основная идея состоит в том, чтобы найти самый длинный повторяющийся суффикс для всех префиксов в строке str.

Length of longest non-repeating substring can be recursively
defined as below.

LCSRe(i, j) stores length of the matching and
            non-overlapping substrings ending 
            with i'th and j'th characters.

If str[i-1] == str[j-1] && (j-i) > LCSRe(i-1, j-1)
     LCSRe(i, j) = LCSRe(i-1, j-1) + 1, 
Else
     LCSRe(i, j) = 0

Where i varies from 1 to n and 
      j varies from i+1 to n

Чтобы избежать наложения, мы должны убедиться, что длина суффикса в любой момент меньше (ji).
Максимальное значение LCSRe (i, j) обеспечивает длину самой длинной повторяющейся подстроки, а сама подстрока может быть найдена с использованием длины и конечного индекса общего суффикса.

Ниже приведена реализация повторения.

C ++

// C ++ программа для поиска самых повторных
// неперекрывающаяся подстрока
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает самый длинный повторяющийся неперекрывающийся
// подстрока в str
string longestRepeatedSubstring(string str)
{

    int n = str.length();

    int LCSRe[n+1][n+1];

  

    // установка всех в 0

    memset(LCSRe, 0, sizeof(LCSRe));

  

    string res; // Для сохранения результата

    int res_length  = 0; // Для сохранения длины результата

  

    // строим стол снизу вверх

    int i, index = 0;

    for (i=1; i<=n; i++)

    {

        for (int j=i+1; j<=n; j++)

        {

            // (ji)> LCSRe [i-1] [j-1] для удаления

            // перекрытие

            if (str[i-1] == str[j-1] &&

                LCSRe[i-1][j-1] < (j - i))

            {

                LCSRe[i][j] = LCSRe[i-1][j-1] + 1;

  

                // обновляем максимальную длину

                // подстрока и обновление отделки

                // индекс суффикса

                if (LCSRe[i][j] > res_length)

                {

                    res_length = LCSRe[i][j];

                    index = max(i, index);

                }

            }

            else

                LCSRe[i][j] = 0;

        }

    }

  

    // Если у нас есть непустой результат, вставьте все

    // символы от первого символа до последнего

    // символ строки

    if (res_length > 0)

        for (i = index - res_length + 1; i <= index; i++)

            res.push_back(str[i-1]);

  

    return res;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    string str = "geeksforgeeks";

    cout << longestRepeatedSubstring(str);

    return 0;

}

Джава

// Java-программа для поиска самого длинного повторения
// неперекрывающаяся подстрока

  

class GFG {

  
// Возвращает самый длинный повторяющийся неперекрывающийся
// подстрока в str

    static String longestRepeatedSubstring(String str) {

        int n = str.length();

        int LCSRe[][] = new int[n + 1][n + 1];

  

        String res = ""; // Для сохранения результата

        int res_length = 0; // Для сохранения длины результата

  

        // строим стол снизу вверх

        int i, index = 0;

        for (i = 1; i <= n; i++) {

            for (int j = i + 1; j <= n; j++) {

                // (ji)> LCSRe [i-1] [j-1] для удаления

                // перекрытие

                if (str.charAt(i - 1) == str.charAt(j - 1)

                        && LCSRe[i - 1][j - 1] < (j - i)) {

                    LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1;

  

                    // обновляем максимальную длину

                    // подстрока и обновление отделки

                    // индекс суффикса

                    if (LCSRe[i][j] > res_length) {

                        res_length = LCSRe[i][j];

                        index = Math.max(i, index);

                    }

                } else {

                    LCSRe[i][j] = 0;

                }

            }

        }

  

        // Если у нас есть непустой результат, вставьте все

        // символы от первого символа до последнего

        // символ строки

        if (res_length > 0) {

            for (i = index - res_length + 1; i <= index; i++) {

                res += str.charAt(i - 1);

            }

        }

  

        return res;

    }

  
// Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) {

        String str = "geeksforgeeks";

        System.out.println(longestRepeatedSubstring(str));

    }

}
// Этот код предоставлен Rajput-JI

Python 3

# Программа Python 3, чтобы найти самый длинный повторяется
# неперекрывающаяся подстрока

  
# Возвращает самый длинный повторяющийся неперекрывающийся
# подстрока в строке

def longestRepeatedSubstring(str):

  

    n = len(str)

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

                for y in range(n + 1)]

  

    res = "" # Сохранить результат

    res_length = 0 # Хранить длину результата

  

    # построение стола снизу вверх

    index = 0

    for i in range(1, n + 1):

        for j in range(i + 1, n + 1):

              

            # (ji)> LCSRe [i-1] [j-1] для удаления

            # перекрытие

            if (str[i - 1] == str[j - 1] and

                LCSRe[i - 1][j - 1] < (j - i)):

                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

  

                # обновление максимальной длины

                # подстрока и обновление отделки

                # индекс суффикса

                if (LCSRe[i][j] > res_length):

                    res_length = LCSRe[i][j]

                    index = max(i, index)

                  

            else:

                LCSRe[i][j] = 0

  

    # Если у нас есть непустой результат, вставьте

    # все символы от первого до

    # последний символ строки

    if (res_length > 0):

        for i in range(index - res_length + 1,

                                    index + 1):

            res = res + str[i - 1]

  

    return res

  
Код водителя

if __name__ == "__main__":

      

    str = "geeksforgeeks"

    print(longestRepeatedSubstring(str))

  
# Этот код предоставлен ita_c

C #

// C # программа для поиска самого длинного повторения
// неперекрывающаяся подстрока

using System;

   

public class GFG {

   
// Возвращает самый длинный повторяющийся неперекрывающийся
// подстрока в str

    static String longestRepeatedSubstring(String str) {

        int n = str.Length;

        int [,]LCSRe = new int[n + 1,n + 1];

   

        String res = ""; // Для сохранения результата

        int res_length = 0; // Для сохранения длины результата

   

        // строим стол снизу вверх

        int i, index = 0;

        for (i = 1; i <= n; i++) {

            for (int j = i + 1; j <= n; j++) {

                // (ji)> LCSRe [i-1] [j-1] для удаления

                // перекрытие

                if (str[i - 1] == str[j - 1]

                        && LCSRe[i - 1,j - 1] < (j - i)) {

                    LCSRe[i,j] = LCSRe[i - 1,j - 1] + 1;

   

                    // обновляем максимальную длину

                    // подстрока и обновление отделки

                    // индекс суффикса

                    if (LCSRe[i,j] > res_length) {

                        res_length = LCSRe[i,j];

                        index = Math.Max(i, index);

                    }

                } else {

                    LCSRe[i,j] = 0;

                }

            }

        }

   

        // Если у нас есть непустой результат, вставьте все

        // символы от первого символа до последнего

        // символ строки

        if (res_length > 0) {

            for (i = index - res_length + 1; i <= index; i++) {

                res += str[i - 1];

            }

        }

   

        return res;

    }

   
// Программа драйвера для проверки вышеуказанной функции

    public static void Main() {

        String str = "geeksforgeeks";

        Console.WriteLine(longestRepeatedSubstring(str));

    }

}
// Этот код предоставлен Rajput-JI


Выход:

geeks

Сложность времени: O (n 2 )
Вспомогательное пространство: O (n 2 )

Ссылки:
http://espressocode.top/longest-common-substring/

Эта статья предоставлена Аюшем Хандури . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Самая длинная повторяющаяся и не перекрывающаяся подстрока

0.00 (0%) 0 votes