두 개의 문자열 'X'와 'Y'가 주어지면 가장 긴 공통 부분 문자열의 길이를 찾으십시오.
예:
입력 : X = techcodeview.com, y = GeeksQuiz
산출 : 5
설명:
가장 긴 공통 부분 문자열은 Geeks이고 길이는 5입니다.입력 : X = abcdxyz, y = xyzabcd
출력 : 4
설명:
가장 긴 공통 부분 문자열은 abcd이고 길이는 4입니다.입력 : X = zxabcdezy, y = yzabcdezx
출력 : 6
설명:
가장 긴 공통 부분 문자열은 abcdez이고 길이는 6입니다.
접근하다:
m과 n을 각각 첫 번째와 두 번째 문자열의 길이로 설정합니다.
ㅏ 간단한 해결책 첫 번째 문자열의 모든 하위 문자열을 하나씩 고려하고 모든 하위 문자열에 대해 두 번째 문자열의 하위 문자열인지 확인하는 것입니다. 최대 길이의 하위 문자열을 추적하세요. O(m^2) 부분 문자열이 있을 것이며 O(n) 시간 내에 문자열이 다른 문자열의 부분 문자열인지 여부를 확인할 수 있습니다(참조: 이것 ). 따라서 이 방법의 전체 시간 복잡도는 O(n * m2)
동적 프로그래밍 O(m*n) 시간에 가장 긴 공통 부분 문자열을 찾는 데 사용할 수 있습니다. 아이디어는 두 문자열의 모든 하위 문자열에 대해 가장 긴 공통 접미사의 길이를 찾아 이 길이를 테이블에 저장하는 것입니다.
가장 긴 공통 접미사는 다음과 같은 최적의 하위 구조 속성을 갖습니다.
마지막 문자가 일치하면 두 길이를 모두 1씩 줄입니다.
- LCSuff(X, Y, m, n) = LCSuff(X, Y, m-1, n-1) + 1 if X[m-1] = Y[n-1]
마지막 문자가 일치하지 않으면 결과는 0입니다. 즉,
- LCSuff(X, Y, m, n) = 0 if (X[m-1] != Y[n-1])
이제 서로 다른 인덱스로 끝나는 서로 다른 하위 문자열의 접미사를 고려합니다.
가장 긴 공통 접미사의 최대 길이는 가장 긴 공통 부분 문자열입니다.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) 여기서 1 <= i <= m 및 1 <= j <= n
다음은 위 솔루션의 반복 구현입니다.
C++
/* Dynamic Programming solution to> >find length of the> >longest common substring */> #include> #include> using> namespace> std;> /* Returns length of longest> >common substring of X[0..m-1]> >and Y[0..n-1] */> int> LCSubStr(>char>* X,>char>* Y,>int> m,>int> n)> {> >// Create a table to store> >// lengths of longest> >// common suffixes of substrings.> >// Note that LCSuff[i][j] contains> >// length of longest common suffix> >// of X[0..i-1] and Y[0..j-1].> >int> LCSuff[m + 1][n + 1];> >int> result = 0;>// To store length of the> >// longest common substring> >/* Following steps build LCSuff[m+1][n+1] in> >bottom up fashion. */> >for> (>int> i = 0; i <= m; i++)> >{> >for> (>int> j = 0; j <= n; j++)> >{> >// The first row and first column> >// entries have no logical meaning,> >// they are used only for simplicity> >// of program> >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;> }> // Driver code> int> main()> {> >char> X[] =>'OldSite:techcodeview.com.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 implementation of> // finding length of longest> // Common substring using> // Dynamic Programming> import> java.io.*;> class> GFG {> >/*> >Returns length of longest common substring> >of X[0..m-1] and Y[0..n-1]> >*/> >static> int> LCSubStr(>char> X[],>char> Y[],>int> m,>int> n)> >{> >// Create a table to store> >// lengths of longest common> >// suffixes of substrings.> >// Note that LCSuff[i][j]> >// contains length of longest> >// common suffix of> >// X[0..i-1] and Y[0..j-1].> >// The first row and first> >// column entries have no> >// logical meaning, they are> >// used only for simplicity of program> >int> LCStuff[][] =>new> int>[m +>1>][n +>1>];> >// To store length of the longest> >// common substring> >int> result =>0>;> >// Following steps build> >// LCSuff[m+1][n+1] in bottom up fashion> >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;> >}> >// Driver Code> >public> static> void> main(String[] args)> >{> >String X =>'OldSite:techcodeview.com.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));> >}> }> // This code is contributed by Sumit Ghosh> |
>
>
파이썬3
# Python3 implementation of Finding> # Length of Longest Common Substring> # Returns length of longest common> # substring of X[0..m-1] and Y[0..n-1]> def> LCSubStr(X, Y, m, n):> ># Create a table to store lengths of> ># longest common suffixes of substrings.> ># Note that LCSuff[i][j] contains the> ># length of longest common suffix of> ># X[0...i-1] and Y[0...j-1]. The first> ># row and first column entries have no> ># logical meaning, they are used only> ># for simplicity of the program.> ># LCSuff is the table with zero> ># value initially in each cell> >LCSuff>=> [[>0> for> k>in> range>(n>+>1>)]>for> l>in> range>(m>+>1>)]> ># To store the length of> ># longest common substring> >result>=> 0> ># Following steps to build> ># LCSuff[m+1][n+1] in bottom up fashion> >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 Code> X>=> 'OldSite:techcodeview.com.org'> Y>=> 'NewSite:GeeksQuiz.com'> m>=> len>(X)> n>=> len>(Y)> print>(>'Length of Longest Common Substring is'>,> >LCSubStr(X, Y, m, n))> # This code is contributed by Soumen Ghosh> |
자바 구조
>
>
씨#
// C# implementation of finding length of longest> // Common substring using Dynamic Programming> using> System;> class> GFG {> >// Returns length of longest common> >// substring of X[0..m-1] and Y[0..n-1]> >static> int> LCSubStr(>string> X,>string> Y,>int> m,>int> n)> >{> >// Create a table to store lengths of> >// longest common suffixes of substrings.> >// Note that LCSuff[i][j] contains length> >// of longest common suffix of X[0..i-1]> >// and Y[0..j-1]. The first row and first> >// column entries have no logical meaning,> >// they are used only for simplicity of> >// program> >int>[, ] LCStuff =>new> int>[m + 1, n + 1];> >// To store length of the longest common> >// substring> >int> result = 0;> >// Following steps build LCSuff[m+1][n+1]> >// in bottom up fashion> >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;> >}> >// Driver Code> >public> static> void> Main()> >{> >String X =>'OldSite:techcodeview.com.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));> >}> }> // This code is contributed by Sam007.> |
>
>
자바스크립트
> // JavaScript implementation of> // finding length of longest> // Common substring using> // Dynamic Programming> >/*> >Returns length of longest common> >substring of X[0..m-1] and Y[0..n-1]> >*/> >function> LCSubStr( X, Y , m , n) {> >// Create a table to store> >// lengths of longest common> >// suffixes of substrings.> >// Note that LCSuff[i][j]> >// contains length of longest> >// common suffix of> >// X[0..i-1] and Y[0..j-1].> >// The first row and first> >// column entries have no> >// logical meaning, they are> >// used only for simplicity of program> > >var> LCStuff => >Array(m + 1).fill().map(()=>배열(n + 1).fill(0));> >// To store length of the longest> >// common substring> >var> result = 0;> >// Following steps build> >// LCSuff[m+1][n+1] in bottom up fashion> >for> (i = 0; i <= m; i++) {> >for> (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;> >}> >// Driver Code> > >var> X =>'OldSite:techcodeview.com.org'>;> >var> Y =>'NewSite:GeeksQuiz.com'>;> >var> m = X.length;> >var> n = Y.length;> >document.write(>'Length of Longest Common Substring is '> +> >LCSubStr(X, Y, m, n));> // This code contributed by Rajput-Ji> > |
>
>
PHP
// Dynamic Programming solution to find // length of the longest common substring // Returns length of longest common // substring of X[0..m-1] and Y[0..n-1] function LCSubStr($X, $Y, $m, $n) { // Create a table to store lengths of // longest common suffixes of substrings. // Notethat LCSuff[i][j] contains length // of longest common suffix of X[0..i-1] // and Y[0..j-1]. The first row and // first column entries have no logical // meaning, they are used only for // simplicity of program $LCSuff = array_fill(0, $m + 1, array_fill(0, $n + 1, NULL)); $result = 0; // To store length of the // longest common substring // Following steps build LCSuff[m+1][n+1] // in bottom up fashion. 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; } // Driver Code $X = 'OldSite:techcodeview.com.org'; $Y = 'NewSite:GeeksQuiz.com'; $m = strlen($X); $n = strlen($Y); echo 'Length of Longest Common Substring is ' . LCSubStr($X, $Y, $m, $n); // This code is contributed by ita_c ?>> |
>
>산출
Length of Longest Common Substring is 10>
시간 복잡도: O(m*n)
보조 공간: O(m*n), m*n의 추가 공간을 차지했기 때문입니다.
또 다른 접근법: (공간 최적화 접근 방식).
위의 접근 방식에서는 2차원 배열의 마지막 행만 사용하므로 다음을 사용하여 공간을 최적화할 수 있습니다.
차원 2*(min(n,m))의 2차원 배열.
다음은 위의 접근 방식을 구현한 것입니다.
C++
알파벳의 숫자
#include> #include> using> namespace> std;> // Function to find the length of the longest LCS> int> LCSubStr(string s, string t,>int> n,>int> m)> {> >// Create DP table> >vectorint>> dp(n + 1, 벡터 |
>
>
자바
// Java implementation of the above approach> import> java.io.*;> class> GFG> {> > >// Function to find the length of the> >// longest LCS> >static> int> LCSubStr(String s,String t,> >int> n,>int> m)> >{> > >// Create DP table> >int> dp[][]=>new> int>[>2>][m+>1>];> >int> res=>0>;> > >for>(>int> i=>1>;i<=n;i++)> >{> >for>(>int> j=>1>;j<=m;j++)> >{> >if>(s.charAt(i->1>)==t.charAt(j->1>))> >{> >dp[i%>2>][j]=dp[(i->1>)%>2>][j->1>]+>1>;> >if>(dp[i%>2>][j]>해상도)> >res=dp[i%>2>][j];> >}> >else> dp[i%>2>][j]=>0>;> >}> >}> >return> res;> >}> > >// Driver Code> >public> static> void> main (String[] args)> >{> >String X=>'OldSite:techcodeview.com.org'>;> >String Y=>'NewSite:GeeksQuiz.com'>;> > >int> m=X.length();> >int> n=Y.length();> > >// Function call> >System.out.println(LCSubStr(X,Y,m,n));> > >}> }> |
>
>
파이썬3
# Python implementation of the above approach> # Function to find the length of the> # longest LCS> def> LCSubStr(s, t, n, m):> > ># Create DP table> >dp>=> [[>0> for> i>in> range>(m>+> 1>)]>for> j>in> range>(>2>)]> >res>=> 0> > >for> i>in> range>(>1>,n>+> 1>):> >for> j>in> range>(>1>,m>+> 1>):> >if>(s[i>-> 1>]>=>=> t[j>-> 1>]):> >dp[i>%> 2>][j]>=> dp[(i>-> 1>)>%> 2>][j>-> 1>]>+> 1> >if>(dp[i>%> 2>][j]>res):> >res>=> dp[i>%> 2>][j]> >else>:> >dp[i>%> 2>][j]>=> 0> >return> res> # Driver Code> X>=> 'OldSite:techcodeview.com.org'> Y>=> 'NewSite:GeeksQuiz.com'> m>=> len>(X)> n>=> len>(Y)> # Function call> print>(LCSubStr(X,Y,m,n))> # This code is contributed by avanitrachhadiya2155> |
>
>
씨#
// C# implementation of the above approach> using> System;> public> class> GFG> {> >// Function to find the length of the> >// longest LCS> >static> int> LCSubStr(>string> s,>string> t,> >int> n,>int> m)> >{> >// Create DP table> >int>[,] dp =>new> int>[2, m + 1];> >int> res = 0;> >for>(>int> i = 1; i <= n; i++)> >{> >for>(>int> j = 1; j <= m; j++)> >{> >if>(s[i - 1] == t[j - 1])> >{> >dp[i % 2, j] = dp[(i - 1) % 2, j - 1] + 1;> >if>(dp[i % 2, j]>해상도)> >res = dp[i % 2, j];> >}> >else> dp[i % 2, j] = 0;> >}> >}> >return> res;> >}> >// Driver Code> >static> public> void> Main (){> >string> X =>'OldSite:techcodeview.com.org'>;> >string> Y =>'NewSite:GeeksQuiz.com'>;> >int> m = X.Length;> >int> n = Y.Length;> >// Function call> >Console.WriteLine(LCSubStr(X,Y,m,n));> >}> }> // This code is contributed by rag2127> |
>
>
자바스크립트
> // JavaScript implementation of the above approach> >// Function to find the length of the> >// longest LCS> >function> LCSubStr(s, t, n, m)> >{> > >// Create DP table> >var> dp = Array(2).fill().map(()=>배열(m+ 1).fill(0));> >var> res = 0;> > >for>(>var> i = 1; i <= n; i++)> >{> >for>(>var> j = 1; j <= m; j++)> >{> >if>(s.charAt(i - 1) == t.charAt(j - 1))> >{> >dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;> >if>(dp[i % 2][j]>해상도)> >res = dp[i % 2][j];> >}> >else> dp[i % 2][j] = 0;> >}> >}> >return> res;> >}> > >// Driver Code> >var> X =>'OldSite:techcodeview.com.org'>;> >var> Y =>'NewSite:GeeksQuiz.com'>;> > >var> m = X.length;> >var> n = Y.length;> > >// Function call> >document.write(LCSubStr(X, Y, m, n));> // This code is contributed by shivanisinghss2110> > |
>
>산출
10>
시간 복잡도: 오(n*m)
보조 공간: O(최소(m,n))
또 다른 접근법: (재귀 사용)
위 접근 방식의 재귀 솔루션은 다음과 같습니다.
C++
// C++ program using to find length of the> // longest common substring recursion> #include> using> namespace> std;> string X, Y;> // Returns length of function f> // or longest common substring> // of X[0..m-1] and 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;> }> // Driver code> int> main()> {> >int> n, m;> >X =>'abcdxyz'>;> >Y =>'xyzabcd'>;> >n = X.size();> >m = Y.size();> >cout << lcs(n, m, 0);> >return> 0;> }> |
>
>
자바
자바의 회귀 표현식
// Java program using to find length of the> // longest common substring recursion> import> java.io.*;> class> GFG {> >static> String X, Y;> >// Returns length of function> >// for longest common> >// substring of X[0..m-1] and 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;> >}> > >// Driver code> >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>));> >}> }> // This code is contributed by Rajput-JI> |
>
>
파이썬3
# Python3 program using to find length of> # the longest common substring recursion> # Returns length of function for longest> # common substring of X[0..m-1] and 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> # Driver code> if> __name__>=>=> '__main__'>:> >X>=> 'abcdxyz'> >Y>=> 'xyzabcd'> >n>=> len>(X)> >m>=> len>(Y)> >print>(lcs(n, m,>0>))> # This code is contributed by Ryuga> |
>
>
씨#
// C# program using to find length> // of the longest common substring> // recursion> using> System;> class> GFG {> >static> String X, Y;> >// Returns length of function for> >// longest common substring of> >// X[0..m-1] and 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;> >}> >// Driver code> >public> static> void> Main()> >{> >int> n, m;> >X =>'abcdxyz'>;> >Y =>'xyzabcd'>;> >n = X.Length;> >m = Y.Length;> >Console.Write(lcs(n, m, 0));> >}> }> // This code is contributed by Rajput-JI> |
>
>
자바스크립트
> >// Javascript program using to find length of the> >// longest common substring recursion> >let X, Y;> > >// Returns length of function f> >// or longest common substring> >// of X[0..m-1] and Y[0..n-1]> >function> lcs(i, j, 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;> >}> > >let n, m;> > >X =>'abcdxyz'>;> >Y =>'xyzabcd'>;> > >n = X.length;> >m = Y.length;> > >document.write(lcs(n, m, 0));> > >// This code is contributed by divyeshrabadiya07.> > |
>
>
PHP
java 배열을 반환하는 방법
// PHP program using to find length of the // longest common substring recursion // Returns length of function for // longest common substring of // X[0..m-1] and 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; } // Driver code $X = 'abcdxyz'; $Y = 'xyzabcd'; $n = strlen($X); $m = strlen($Y); echo lcs($n, $m, 0, $X, $Y); // This code is contributed // by rathbhupendra ?>> |
>
>산출
4>
시간 복잡도 : O(2^최대(m,n)) 함수가 X[i-1] != Y[j-1]의 문자일 때 두 개의 재귀 호출(lcs(i, j-1, 0) 및 lcs(i-1, j, 0))을 수행하기 때문입니다. 따라서 최악의 경우 시간 복잡도는 2^N으로 제공됩니다. 여기서 N = max(m, n), m 및 n은 X 및 Y 문자열의 길이입니다.
보조 공간: O(1): 함수 호출은 추가 공간을 사용하지 않기 때문입니다(함수는 일반적으로 보조 공간에서 고려하지 않는 재귀 호출 스택을 사용하고 있습니다).