本文共 1806 字，大约阅读时间需要 6 分钟。
JAVA算法：最长重复子串问题（JAVA解题）
Given a string str, find the longest repeating non-overlapping substring in it. In other words find 2 identical substrings of maximum length which do not overlap. If there exists more than one such substring return any of them.
Examples:
Input : str = "geeksforgeeks"
Output : geeksInput : str = "aab"
Output : aInput : str = "aabaabaaba"
Output : aabaInput : str = "aaaaaaaaaaa"
Output : aaaaaInput : str = "banana"
Output : an or na算法设计
package com.bean.algorithm.basic;public class LongestRepeatingSubstring { // 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 = "aabaabaaba"; System.out.println(longestRepeatedSubstring(str)); }} 程序运行结果：
aaba
转载地址：http://nntdi.baihongyu.com/