Given a text string, find Longest Repeated Substring in the text. If there are more than one Longest Repeated Substrings, get any one of them.
Longest Repeated Substring in GEEKSFORGEEKS is: GEEKS Longest Repeated Substring in AAAAAAAAAA is: AAAAAAAAA Longest Repeated Substring in ABCDEFG is: No repeated substring Longest Repeated Substring in ABABABA is: ABABA Longest Repeated Substring in ATCGATCGA is: ATCGA Longest Repeated Substring in banana is: ana Longest Repeated Substring in abcpqrabpqpq is: ab (pq is another LRS here)
Solution 1:
Using Suffix Array. Time complexity: O(nlogn), Space complexity: O(n)
// return the longest repeated string in s public String lrs(String s) { // form the N suffixes int N = s.length(); String[] suffixes = new String[N]; for (int i = 0; i < N; i++) { suffixes[i] = s.substring(i, N); } // sort them Arrays.sort(suffixes); // find longest repeated substring by comparing adjacent sorted suffixes String lrs = ""; for (int i = 0; i < N - 1; i++) { String x = lcp(suffixes[i], suffixes[i+1]); if (x.length() > lrs.length()) lrs = x; } return lrs; } // return the longest common prefix of s and t public String lcp(String s, String t) { int n = Math.min(s.length(), t.length()); for (int i = 0; i < n; i++) { if (s.charAt(i) != t.charAt(i)) return s.substring(0, i); } return s.substring(0, n); }
Reference:
http://introcs.cs.princeton.edu/java/42sort/LRS.java.html
Solution 2:
Using Suffix Tree. Time complexity: O(n), Space complexity: O(n)
Reference:
http://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/
相关推荐
c语言入门 c语言_leetcode题解03-longest-substring-without-repeating-characters
js js_leetcode题解3-longest-substring-without-repeating-characters.js
c语言入门 c语言_leetcode题解05-longest-palindromic-substring.c
js js_leetcode题解之5-longest-palindromic-substring.js
c c语言_leetcode 0003_longest_substring_without_repeat.zip
java入门 java_leetcode题解之003_Longest_Substring_Without_Repeating
本题涉及的核心知识点是“最长公共子串”(Longest Common Substring),这是一个经典的动态规划问题。以下将详细解析这个问题及其解决方案。 首先,我们需要理解“最长公共子串”的概念。在两个给定的字符串s1和s2...
c c语言_leetcode 0005_longest_palindromic_substring.zip
java入门 java_leetcode题解之005_Longest_Palindromic_Substring
在IT领域,字符串处理是常见的任务之一,尤其是在编程语言如Java中。...在压缩包文件"longest-non-repeated-substring-master"中,可能包含了这个算法的详细实现和其他相关测试案例,可以作为学习和研究的参考。
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
标题“POJ2533-Longest Ordered Subsequence”是指北京大学在线判题系统POJ上的一道编程题目,其核心任务是寻找一个序列中最长的有序子序列。描述中的“解题报告+AC代码”表明这个压缩包包含了对这道问题的解答思路...
js js_leetcode题解之32-longest-valid-parentheses.js
js js_leetcode题解之14-longest-common-prefix.js
c语言入门 C语言_leetcode题解之32-longest-valid-parentheses.c
c语言入门 C语言_leetcode题解之14-longest-common-prefix.c
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...