给一根绳子 str ，找到其中最长的重复非重叠子串。换句话说，找到两个相同的最大长度的子串，它们不重叠。如果存在多个子字符串，则返回其中任何一个子字符串。 例如：
null
Input : str = "geeksforgeeks"Output : geeksInput : str = "aab"Output : aInput : str = "aabaabaaba"Output : aabaInput : str = "aaaaaaaaaaa"Output : aaaaaInput : 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 recursivelydefined 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) = 0Where i varies from 1 to n and j varies from i+1 to n
为了避免重叠，我们必须确保后缀的长度在任何时刻都小于（j-i）。 LCSRe（i，j）的最大值提供了最长重复子串的长度，可以使用公共后缀的长度和结束索引找到子串本身。 下面是递归的实现。
C++
// C++ program to find the longest repeated // non-overlapping substring #include<bits/stdc++.h> using namespace std; // Returns the longest repeating non-overlapping // substring in str string longestRepeatedSubstring(string str) { int n = str.length(); int LCSRe[n+1][n+1]; // Setting all to 0 memset (LCSRe, 0, sizeof (LCSRe)); string res; // To store result int res_length = 0; // To store length of result // building table in bottom-up manner int i, index = 0; for (i=1; i<=n; i++) { for ( int j=i+1; j<=n; j++) { // (j-i) > LCSRe[i-1][j-1] to remove // overlapping if (str[i-1] == str[j-1] && 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 = index - res_length + 1; i <= index; i++) res.push_back(str[i-1]); return res; } // Driver program to test the above function int main() { string str = "geeksforgeeks" ; cout << longestRepeatedSubstring(str); return 0; } |
JAVA
// Java program to find the longest repeated // non-overlapping substring class GFG { // Returns the longest repeating non-overlapping // substring in str static String longestRepeatedSubstring(String str) { int n = str.length(); int LCSRe[][] = new int [n + 1 ][n + 1 ]; String res = "" ; // To store result int res_length = 0 ; // To store length of result // building table in bottom-up manner int i, index = 0 ; for (i = 1 ; i <= n; i++) { for ( int j = i + 1 ; j <= n; j++) { // (j-i) > LCSRe[i-1][j-1] to remove // overlapping 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 ; // 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 = Math.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 = index - res_length + 1 ; i <= index; i++) { res += str.charAt(i - 1 ); } } return res; } // Driver program to test the above function public static void main(String[] args) { String str = "geeksforgeeks" ; System.out.println(longestRepeatedSubstring(str)); } } // This code is contributed by Rajput-JI |
Python 3
# Python 3 program to find the longest repeated # non-overlapping substring # Returns the longest repeating non-overlapping # substring in str 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 |
C#
// C# program to find the longest repeated // non-overlapping substring using System; public class GFG { // Returns the longest repeating non-overlapping // substring in str static String longestRepeatedSubstring(String str) { int n = str.Length; int [,]LCSRe = new int [n + 1,n + 1]; String res = "" ; // To store result int res_length = 0; // To store length of result // building table in bottom-up manner int i, index = 0; for (i = 1; i <= n; i++) { for ( int j = i + 1; j <= n; j++) { // (j-i) > LCSRe[i-1][j-1] to remove // overlapping if (str[i - 1] == str[j - 1] && 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 = Math.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 = index - res_length + 1; i <= index; i++) { res += str[i - 1]; } } return res; } // Driver program to test the above function public static void Main() { String str = "geeksforgeeks" ; Console.WriteLine(longestRepeatedSubstring(str)); } } // This code is contributed by Rajput-JI |
Javascript
<script> // Javascript program to find the longest repeated // non-overlapping substring // Returns the longest repeating non-overlapping // substring in str function longestRepeatedSubstring(str) { let n = str.length; let LCSRe = new Array(n+1); for (let i = 0; i < n + 1; i++) { LCSRe[i] = new Array(n+1); } for (let i = 0; i < n + 1; i++) { for (let j = 0; j < n + 1; j++) { LCSRe[i][j] = 0; } } let res = "" ; // To store result let res_length = 0; // To store length of result // building table in bottom-up manner let i, index = 0; for (i = 1; i <= n; i++) { for (let j = i + 1; j <= n; j++) { // (j-i) > LCSRe[i-1][j-1] to remove // overlapping if (str[i-1] == str[j-1] && 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 = Math.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 = index - res_length + 1; i <= index; i++) { res += str.charAt(i - 1); } } return res; } // Driver program to test the above function let str= "geeksforgeeks" ; document.write(longestRepeatedSubstring(str)); // This code is contributed by rag2127 </script> |
输出：
geeks
时间复杂性： O（n） 2. ) 辅助空间： O（n） 2. ) 参考资料： https://www.geeksforgeeks.org/longest-common-substring/ 本文由 阿尤什·坎杜里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
