# 1062. Longest Repeating Substring



實際上這題跟 718 差不多, 差別在於因為要找的是 repeat sunstring, 所以我們立刻可以想到一樣用兩個字串來比較看看, 這樣就跟 718 題目變的一樣了, 要找的是 longest common substring(subarray)

但稍微有點不一樣, 也就是兩個字串在同一個位置上不能視為 common (看題目的意思可以了解



<figure><img src="https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2Fx6XpFdwHGeo5fH8r9Xr9%2Fimage.png?alt=media&#x26;token=1365423a-c045-4d69-b291-eac00b3f5783" alt=""><figcaption></figcaption></figure>

## DP

T: O(n^2)

S: O(n^2)

```java
class Solution {
    public int longestRepeatingSubstring(String s) {
        int n = s.length();
        s = "#" + s;
        int[][] dp = new int[n+1][n+1];
        dp[0][0] = 0;
        
        int max = 0; // 最少長度是 0
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max;
    }
}

/*
seen s as two string to compare

xxx[xxxxi]
x[xxxxj]

dp[i][j]: string s1 with ending i and string s2 with ending j, has the common substring len

if (S[i] == S[j]) so 

if (S[i] == S[j]) dp[i][j] = dp[i-1][j-1] + 1;
*/
```
