[Swift-2019力扣杯春季决赛]3. 最长重复子串

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10745819.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

给定字符串 S，找出最长重复子串的长度。如果不存在重复子串就返回 0。

示例 1：

输入："abcd"
输出：0
解释：没有重复子串。

示例 2：

输入："abbaba"
输出：2
解释：最长的重复子串为 "ab" 和 "ba"，每个出现 2 次。

示例 3：

输入："aabcaabdaab"
输出：3
解释：最长的重复子串为 "aab"，出现 3 次。

示例 4：

输入："aaaaa"
输出：4
解释：最长的重复子串为 "aaaa"，出现 2 次。

提示：

1. 字符串 S 仅包含从 'a' 到 'z' 的小写英文字母。
2. 1 <= S.length <= 1500

---

920 ms

class Solution {
    var lcp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:1505),count:1505)
    func longestRepeatingSubstring(_ S: String) -> Int {
        var n:Int = S.count
        var ans:Int = 0
        var arrS:[Character] = Array(S)
        for i in stride(from:n - 1,through:0,by:-1)
        {
            for j in (i + 1)..<n
            {
                if arrS[i] == arrS[j]
                {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1
                }
                else
                {
                    lcp[i][j] = 0
                }
                ans=max(ans,lcp[i][j])
            }        
        }
        return ans        
    }
}