# 1062. Longest Repeating Substring

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

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

<figure><img src="/files/1TEzbRHTEwIyA7usJdwD" 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;
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/pattern-matching-dp/1062.-longest-repeating-substring.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.