LeetCode 1062. Longest Repeating Substring

原题链接在这里：https://leetcode.com/problems/longest-repeating-substring/

题目：

Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.

Example 1:

Input: "abcd"
Output: 0
Explanation: There is no repeating substring.

Example 2:

Input: "abbaba"
Output: 2
Explanation: The longest repeating substrings are "ab" and "ba", each of which occurs twice.

Example 3:

Input: "aabcaabdaab"
Output: 3
Explanation: The longest repeating substring is "aab", which occurs 3 times.

Example 4:

Input: "aaaaa"
Output: 4
Explanation: The longest repeating substring is "aaaa", which occurs twice.

Note:

1. The string S consists of only lowercase English letters from ‘a‘ - ‘z‘.
2. 1 <= S.length <= 1500

题解：

Let dp[i][j] denotes S, up to i, and up to j<i, the number of common suffix.

When j and i are pointing to same char, dp[i][j] = dp[i-1][j-1]+1.

Maintain the maximum.

Time Complexity: O(n^2). n = S.length().

Space: O(n^2).

AC Java:

 1 class Solution {
 2     public int longestRepeatingSubstring(String S) {
 3         if(S == null || S.length() == 0){
 4             return 0;
 5         }
 6         
 7         int n = S.length();
 8         int res = 0;
 9         
10         int [][] dp = new int[n+1][n+1];
11         for(int i = 1; i<=n; i++){
12             for(int j = 1; j<i; j++){
13                 if(S.charAt(i-1) == S.charAt(j-1)){
14                     dp[i][j] = dp[i-1][j-1]+1;
15                     res = Math.max(res, dp[i][j]);            
16                 }
17             }
18         }
19         
20         return res;
21     }
22 }

LeetCode 1062. Longest Repeating Substring

原文：https://www.cnblogs.com/Dylan-Java-NYC/p/11986893.html