关于Longest Repeated Substring的一道题

最近约了一家大厂senior的SDE做了一下mock interview，遇到了一道题，题目是这样：

Find the longest repeated substring in a string and output the number of repeated times for that longest repeated substring.

String: “how are you, hey guys, hey Hannah, hey Frank, Spencer is the best person in my class”

Expected output
‘, hey ‘  3

面试的时候没有想太多，直接先找Longest Duplicate substring - https://leetcode.com/problems/longest-duplicate-substring/. 然后loop了一遍string算frequency。想请教下各位大佬有没有什么更有的解法？如果可以的话还请贴一下代码。

PS: 这道题还有个 follow up，我时间不够了，没来得及写，简单说了下思路，题目如下：
compare two strings, and find what is the longest repeated common substring within the two strings, and output the total repeated times.

String 1:    “If you look at what you have in life, you'll always have more. If you look at what you don’t have in life, you'll never have enough.”
String 2:    “When you have something in your mind, just do it, otherwise you don’t have the chance to succeed. If you do something, you don’t have to blame yourself later”

Rule: a substring which exists both in String 1 and String 2.

Expected output:
Longest  repeated substring: “ you don’t have “, repeat times: 3

来问下大家有什么思路吗？

后缀自动机

补充内容 (2022-02-26 13:31 +08:00):
nlogn 的话，后缀数组/二分hash应该也都可以

简单的办法就是用hash

二分长度 然后滚动hash 时间复杂度O(nlogn) 感觉应该是这样的
大致写了下，能过样例了。我这里偷懒用了stringbuilder，理论上要换成滚动hash也就是Rabin-Karp法就是真正的O(nlogn)了

1. // "static void main" must be defined in a public class.
   
2. public class Main {
   
3.     public static void main(String[] args) {
   
4.         var tmp = findLongestPatternAndTime(", hey guys, hey Hannah, hey 1");
   
5.         System.out.println("pattern = \'" + tmp[0] + "\' , times = " + tmp[1]);
   
6.     }
   
7.     static String pattern;
   
8.     static int times;
   
9.     private static String[] findLongestPatternAndTime(String s) {
   
10.         pattern = "";
    
11.         int left = 0, right = s.length() / 2;
    
12.         while (left <= right) {
    
13.             int mid = left + (right - left) / 2;
    
14.             if (valid(s, mid)) {
    
15.                 left = mid + 1;
    
16.             } else {
    
17.                 right = mid - 1;
    
18.             }
    
19.         }
    
20.         return new String[] {pattern, String.valueOf(times)};
    
21.     }
    
22.    
    
23.     // varify whether exist a pattern, of which length is len
    
24.     private static boolean valid(String s, int len) {
    
25.         var strToPos = new HashMap<String, List<Integer>> ();
    
26.         var sb = new StringBuilder(s.substring(0, len));
    
27.         boolean found = false;
    
28.         for (int i = 0; i < s.length() - len; ++i) {
    
29.             var p = sb.toString();
    
30.             strToPos.computeIfAbsent(p, x -> new ArrayList<> ());
    
31.             var list = strToPos.get(p);
    
32.             if (list.isEmpty() || i - list.get(list.size() - 1) >= len) {
    
33.                 list.add(i);
    
34.             }
    
35.             if (list.size() > 1) {
    
36.                 pattern = p;
    
37.                 times = list.size();
    
38.                 found = true;
    
39.             }
    
40.             sb.delete(0, 1);
    
41.             sb.append(s.charAt(i + len));
    
42.         }
    
43.         return found;
    
44.     }
    
45. }

复制代码

https://en.wikipedia.org/wiki/Longest_repeated_substring_problem