Рубрики

Длинная общая подстрока | DP-29

Учитывая две строки 'X' и 'Y', найдите длину самой длинной общей подстроки.

Примеры :

Input : X = “GeeksforGeeks”, y = “GeeksQuiz”
Output : 5
The longest common substring is “Geeks” and is of length 5.

Input : X = “abcdxyz”, y = “xyzabcd”
Output : 4
The longest common substring is “abcd” and is of length 4.

Input : X = “zxabcdezy”, y = “yzabcdezx”
Output : 6
The longest common substring is “abcdez” and is of length 6.

Пусть m и n будут длинами первой и второй строк соответственно.

Простое решение состоит в том, чтобы один за другим рассматривать все подстроки первой строки и для каждой подстроки проверять, является ли она подстрокой во второй строке. Следите за максимальной длиной подстроки. Будет O (m ^ 2) подстрок, и мы можем выяснить, является ли строка подстрокой в другой строке за O (n) время (см. Это ). Таким образом, общая временная сложность этого метода будет O (n * m 2 )

Динамическое программирование может использоваться для нахождения самой длинной общей подстроки за время O (m * n). Идея состоит в том, чтобы найти длину самого длинного общего суффикса для всех подстрок обеих строк и сохранить эти длины в таблице.

The longest common suffix has following optimal substructure property.

If last characters match, then we reduce both lengths by 1
LCSuff(X, Y, m, n) = LCSuff(X, Y, m-1, n-1) + 1 if X[m-1] = Y[n-1]
If last characters do not match, then result is 0, i.e.,
LCSuff(X, Y, m, n) = 0 if (X[m-1] != Y[n-1])

Now we consider suffixes of different substrings ending at different indexes.
The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m and 1 <= j <= n

Ниже приведена итеративная реализация вышеуказанного решения.

C ++

/ * Динамическое программирование, чтобы найти длину

   самая длинная общая подстрока * /

#include<iostream>
#include<string.h>

using namespace std;

  
/ * Возвращает длину самой длинной общей подстроки X [0..m-1]

   и Y [0..n-1] * /

int LCSubStr(char *X, char *Y, int m, int n)

{

    // Создать таблицу для хранения длин

    // общие суффиксы подстрок. Обратите внимание, что

    // LCSuff [i] [j] содержит длину самого длинного

    // общий суффикс X [0..i-1] и Y [0..j-1].

  

    int LCSuff[m+1][n+1];

    int result = 0;  // Для хранения длины

                     // самая длинная общая подстрока

  

    / * Следующими шагами соберите LCSuff [m + 1] [n + 1] в

        снизу вверх мода. * /

    for (int i=0; i<=m; i++)

    {

        for (int j=0; j<=n; j++)

        {

  

            // Первая строка и первый столбец

            // записи не имеют логического значения,

            // они используются только для простоты

            // программы

            if (i == 0 || j == 0)

                LCSuff[i][j] = 0;

  

            else if (X[i-1] == Y[j-1])

            {

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

                result = max(result, LCSuff[i][j]);

            }

            else LCSuff[i][j] = 0;

        }

    }

    return result;

}

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

int main()

{

    char X[] = "OldSite:GeeksforGeeks.org";

    char Y[] = "NewSite:GeeksQuiz.com";

  

    int m = strlen(X);

    int n = strlen(Y);

  

    cout << "Length of Longest Common Substring is " 

         << LCSubStr(X, Y, m, n);

    return 0;

}

Джава

// Java-реализация определения длины самого длинного
// Общая подстрока с использованием динамического программирования

public class LongestCommonSubSequence 

{

    / *

       Возвращает длину самой длинной общей подстроки

       из X [0..m-1] и Y [0..n-1]

    * /

    static int LCSubStr(char X[], char Y[], int m, int n) 

    {

        // Создать таблицу для хранения длинных общих суффиксов

        // подстроки. Обратите внимание, что LCSuff [i] [j] содержит длину самого длинного

        // общий суффикс X [0..i-1] и Y [0..j-1]. Первый ряд и

        // записи первого столбца не имеют логического значения, они используются только

        // для простоты программы

        int LCStuff[][] = new int[m + 1][n + 1];

        int result = 0// Для хранения длины самой длинной общей подстроки

          

        // Следующие шаги строят LCSuff [m + 1] [n + 1] снизу вверх

        for (int i = 0; i <= m; i++) 

        {

            for (int j = 0; j <= n; j++) 

            {

                if (i == 0 || j == 0)

                    LCStuff[i][j] = 0;

                else if (X[i - 1] == Y[j - 1])

                {

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

                    result = Integer.max(result, LCStuff[i][j]);

                

                else

                    LCStuff[i][j] = 0;

            }

        }

        return result;

    }

      

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

    public static void main(String[] args) 

    {

        String X = "OldSite:GeeksforGeeks.org";

        String Y = "NewSite:GeeksQuiz.com";

  

        int m = X.length();

        int n = Y.length();

  

        System.out.println("Length of Longest Common Substring is "

                + LCSubStr(X.toCharArray(), Y.toCharArray(), m, n));

    }

}

  
// Этот код предоставлен Sumit Ghosh

python3

# Python3 реализация Finding
# Длина самой длинной общей подстроки

  
# Возвращает длину самого длинного общего
# подстрока из X [0..m-1] и Y [0..n-1]

def LCSubStr(X, Y, m, n):

      

    # Создать таблицу для хранения длин

    # самые длинные распространенные суффиксы подстрок.

    # Обратите внимание, что LCSuff [i] [j] содержит

    # длина самого длинного общего суффикса

    # X [0 ... i-1] и Y [0 ... j-1]. Первый

    # строки и записи первого столбца не имеют

    # логическое значение, они используются только

    # для простоты программы.

      

    # LCSuff - таблица с нулем

    # значение изначально в каждой ячейке

    LCSuff = [[0 for k in range(n+1)] for l in range(m+1)]

      

    # Для хранения длины

    # самая длинная общая подстрока

    result = 0 

  

    # Следующие шаги для сборки

    # LCSuff [m + 1] [n + 1] снизу вверх

    for i in range(m + 1):

        for j in range(n + 1):

            if (i == 0 or j == 0):

                LCSuff[i][j] = 0

            elif (X[i-1] == Y[j-1]):

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

                result = max(result, LCSuff[i][j])

            else:

                LCSuff[i][j] = 0

    return result

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

X = 'OldSite:GeeksforGeeks.org'

Y = 'NewSite:GeeksQuiz.com'

  

m = len(X)

n = len(Y)

  

print('Length of Longest Common Substring is',

                      LCSubStr(X, Y, m, n))

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

C #

// C # реализация определения длины самого длинного
// Общая подстрока с использованием динамического программирования

using System;

  

class GFG {

       

    // Возвращает длину самого длинного общего

    // подстрока из X [0..m-1] и Y [0..n-1]

    static int LCSubStr(string X, string Y,

                                 int m, int n)

    {

          

        // Создать таблицу для хранения длин

        // самые длинные общие суффиксы подстрок.

        // Обратите внимание, что LCSuff [i] [j] содержит длину

        // самого длинного общего суффикса X [0..i-1]

        // и Y [0..j-1]. Первый ряд и первый

        // записи столбцов не имеют логического значения,

        // они используются только для простоты

        // программа

        int[, ] LCStuff = new int[m + 1, n + 1];

          

        // Для хранения длины самого длинного общего

        // подстрока

        int result = 0; 

  

        // Следующие шаги строят LCSuff [m + 1] [n + 1]

        // снизу вверх

        for (int i = 0; i <= m; i++) {

            for (int j = 0; j <= n; j++) {

                if (i == 0 || j == 0)

                    LCStuff[i, j] = 0;

                else if (X[i - 1] == Y[j - 1]) {

                    LCStuff[i, j] = 

                            LCStuff[i - 1, j - 1] + 1;

                              

                    result = Math.Max(result, 

                                      LCStuff[i, j]);

                }

                else

                    LCStuff[i, j] = 0;

            }

        }

          

        return result;

    }

  

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

    public static void Main()

    {

        String X = "OldSite:GeeksforGeeks.org";

        String Y = "NewSite:GeeksQuiz.com";

  

        int m = X.Length;

        int n = Y.Length;

  

        Console.Write("Length of Longest Common"

        + " Substring is " + LCSubStr(X, Y, m, n));

    }

  
}

  
// Этот код предоставлен Sam007.

PHP

<?php 
// Динамическое программирование для поиска решения
// длина самой длинной общей подстроки

  
// Возвращает длину самого длинного общего
// подстрока из X [0..m-1] и Y [0..n-1]

function LCSubStr($X, $Y, $m, $n)

{

    // Создать таблицу для хранения длин

    // самые длинные общие суффиксы подстрок.

    // Обратите внимание, что LCSuff [i] [j] содержит длину

    // самого длинного общего суффикса X [0..i-1]

    // и Y [0..j-1]. Первый ряд и

    // записи первого столбца не имеют логического

    // имеется ввиду, они используются только для

    // простота программы

    $LCSuff = array_fill(0, $m + 1,

              array_fill(0, $n + 1, NULL));

    $result = 0; // Для хранения длины

                 // самая длинная общая подстрока

  

    // Следующие шаги строят LCSuff [m + 1] [n + 1]

    // в моде снизу вверх.

    for ($i = 0; $i <= $m; $i++)

    {

        for ($j = 0; $j <= $n; $j++)

        {

            if ($i == 0 || $j == 0)

                $LCSuff[$i][$j] = 0;

  

            else if ($X[$i - 1] == $Y[$j - 1])

            {

                $LCSuff[$i][$j] = $LCSuff[$i - 1][$j - 1] + 1;

                $result = max($result

                              $LCSuff[$i][$j]);

            }

            else $LCSuff[$i][$j] = 0;

        }

    }

    return $result;

}

  
// Код драйвера

$X = "OldSite:GeeksforGeeks.org";

$Y = "NewSite:GeeksQuiz.com";

  

$m = strlen($X);

$n = strlen($Y);

  

echo "Length of Longest Common Substring is "

                      LCSubStr($X, $Y, $m, $n);

                        
// Этот код предоставлен ita_c
?>


Выход:

Length of Longest Common Substring is 10

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

Другой подход: (с использованием рекурсии)
Вот рекурсивное решение вышеуказанного подхода.

C ++

// Программа на C ++, используемая для определения длины
// самая длинная общая рекурсия подстроки
#include <iostream>

  

using namespace std;

  
string X,Y;

  
// Возвращает длину функции для самого длинного общего
// подстрока из X [0..m-1] и Y [0..n-1]

int lcs(int i, int j, int count) 

{

      

    if (i == 0 || j == 0)

        return count;

          

    if (X[i-1] == Y[j-1]) {

        count = lcs(i - 1, j - 1, count + 1);

    }

        count = max(count, max(lcs( i, j - 1, 0), lcs( i - 1, j, 0)));

    return count;

}

  
// Код драйвера

int main()

{

int n,m;

  

X = "abcdxyz"

Y = "xyzabcd";

  
n=X.size();
m=Y.size();

  
cout<<lcs(n,m,0);

  

    return 0;

}

Джава

// Java-программа, используемая для определения длины
// самая длинная общая рекурсия подстроки

  

class GFG {

  

    static String X, Y;

// Возвращает длину функции для самого длинного общего
// подстрока из X [0..m-1] и Y [0..n-1]

    static int lcs(int i, int j, int count) {

  

        if (i == 0 || j == 0) {

            return count;

        }

  

        if (X.charAt(i - 1) == Y.charAt(j - 1)) {

            count = lcs(i - 1, j - 1, count + 1);

        }

        count = Math.max(count, Math.max(lcs(i, j - 1, 0),

                            lcs(i - 1, j, 0)));

        return count;

    }

// Код драйвера

    public static void main(String[] args) {

        int n, m;

        X = "abcdxyz";

        Y = "xyzabcd";

  

        n = X.length();

        m = Y.length();

  

        System.out.println(lcs(n, m, 0));

    }

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

python3

# Python3 программа использует для определения длины
# самая длинная общая рекурсия подстроки

  
# Возвращает длину функции для самого длинного
# общая подстрока X [0..m-1] и Y [0..n-1]

def lcs(i, j, count) : 

      

    if (i == 0 or j == 0) : 

        return count 

          

    if (X[i - 1] == Y[j - 1]) :

        count = lcs(i - 1, j - 1, count + 1

      

    count = max(count, max(lcs( i, j - 1, 0), 

                           lcs( i - 1, j, 0))) 

  

    return count

  
# Код драйвера

if __name__ == "__main__" :

  

    X = "abcdxyz"

    Y = "xyzabcd"

  

    n = len(X)

    m = len(Y)

  

    print(lcs(n, m, 0)) 

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

C #

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

using System;

  

class GFG

static String X, Y;

  
// Возвращает длину функции для
// самая длинная общая подстрока
// X [0..m-1] и Y [0..n-1]

static int lcs(int i, int j, int count) 

{

  

    if (i == 0 || j == 0)

    {

        return count;

    }

  

    if (X[i - 1] == Y[j - 1]) 

    {

        count = lcs(i - 1, j - 1, count + 1);

    }

    count = Math.Max(count, Math.Max(lcs(i, j - 1, 0), 

                                     lcs(i - 1, j, 0)));

    return count;

}

  
// Код драйвера

public static void Main() 

{

    int n, m;

    X = "abcdxyz";

    Y = "xyzabcd";

  

    n = X.Length;

    m = Y.Length;

  

    Console.Write(lcs(n, m, 0));

}
}

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

PHP

<?php
// PHP-программа, используемая для определения длины
// самая длинная общая рекурсия подстроки

  
// Возвращает длину функции для
// самая длинная общая подстрока
// X [0..m-1] и Y [0..n-1]

function lcs($i, $j, $count, &$X, &$Y

    if ($i == 0 || $j == 0) 

        return $count

          

    if ($X[$i - 1] == $Y[$j - 1]) 

    

        $count = lcs($i - 1, $j - 1, 

                     $count + 1, $X, $Y); 

    

        $count = max($count, lcs($i, $j - 1, 0, $X, $Y), 

                             lcs($i - 1, $j, 0, $X, $Y)); 

    return $count

  
// Код драйвера

$X = "abcdxyz"

$Y = "xyzabcd"

  

$n = strlen($X); 

$m = strlen($Y); 

  

echo lcs($n, $m, 0, $X, $Y); 

  
// Этот код добавлен
// ратбхупендра
?>


Выход:

4

Ссылки: http://en.wikipedia.org/wiki/Longest_common_substring_problem

Самая длинная подстрока также может быть найдена за O (n + m) время с использованием Suffix Tree. Мы расскажем о решении на основе Suffix Tree в отдельном посте.

Упражнение: Приведенное выше решение печатает только длину самой длинной общей подстроки. Расширьте решение, чтобы распечатать подстроку также.

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

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

Длинная общая подстрока | DP-29

0.00 (0%) 0 votes