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/
相关推荐
前端工程师面试
最长非重复子串没有重复字符的最长子串的长度( )
答案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 版本
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
leetcode 答案最长子串 来自 leetcode.com 的问题。 描述: 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: 输入:“abcabcbb” 输出:3 解释:答案是“abc”,长度为3。
leetcode 2 最长子串 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. 示例 2: ...来源:
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also ...substri
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 ...s.substring(i, ...isPalindrome(s.substring(i, j))) { max = s.substring(i, j); } } } re
最长公共子序列演示程序,算法分析与设计,动态规划算法
前端工程师面试
Substring Without Repeating Characters.cpp │ │ ├── 004 - Median of Two Sorted Arrays.cpp │ │ └── 005 - Longest Palindromic Substring.cpp │ └── python │ ├── 001 - Two Sum....
./0003-longest-substring-without-repeating-characters.cpp ./0004-median-of-two-sorted-arrays.cpp ./0005-longest-palindromic-substring.cpp ./0006-zigzag-conversion.cpp ./0007-reverse-integer.cpp ./0008...
3-longest-substring-without-repeating-characters 7 cargo run --bin 7-reverse-integer 9 cargo run --bin 9-palindrome-number 13 cargo run --bin 13-roman-to-integer 14 cargo run --bin 14-longest-common-...