寻找一个字符串的重复子串后缀数组

川长思鸟来 2022-05-22 10:17 219阅读 0赞

# 什么是后缀数组 #

令字符串 *S*=*S*\[1\]*S*\[2\]...*S*\[*n*\]  S = S \[ 1 \] S \[ 2 \] . . . S \[ n \] ， *S*\[*i*,*j*\]  S \[ i , j \] 表示*S*  S 的子字符串，下标从*i*  i 到 *j*  j 。

*S*  S 的后缀数组*A*  A 被定义为一个数组，内容是 *S*  S 的所有后缀经过字典排序后的起始下标。

对于所有的有：1<*i*≤*n*:*S*\[*A*\[*i*−1\],*n*\]<*S*\[*A*\[*i*\],*n*\]  1 < i ≤ n : S \[ A \[ i − 1 \] , n \] < S \[ A \[ i \] , n \] 。

![这里写图片描述][70]

![这里写图片描述][70 1]

# 求一个字符串的重复字串 #

# -*- coding: utf-8 -*-
    
    # !/usr/bin/env python
    
    # Time: 2018/6/21 20:51
    
    # Author: sty
    
    # File: 4.py
    
    import sys
    
    def get_common_len(str1, str2):
        len1 = len(str1)
        len2 = len(str2)
        min_len = min(len1, len2)
        res_i = 0
        for i in range(min_len):
            res_i = i
            if str1[i] != str2[i]:
                break
        return res_i + 1
    
    
    if __name__ == "__main__":
        str = sys.stdin.readline().strip()
        strs = []
        for i in range(len(str)):
            strs.append(str[i:])
        strs.sort()
        max_len = 0
        for i in range(len(strs) - 1):
            len_temp = get_common_len(strs[i], strs[i + 1])
            max_len = max(max_len, len_temp)
        print(max_len)

# 参考链接 #

[算法设计 - 寻找一个字符串的重复子串LRS][- _LRS]  
[给定一个字符串，求出其最长的重复子串的长度][Link 1]  
[WIKI][]  
[https://blog.csdn.net/xwchao2014/article/details/47754613][https_blog.csdn.net_xwchao2014_article_details_47754613]

[70]: /images/20220522/3d1290b6b943463cb0d09d67eaea1fab.png
[70 1]: /images/20220522/79aee1a063ee4eb1a16e237ad572aa59.png
[- _LRS]: https://segmentfault.com/a/1190000002646526
[Link 1]: https://blog.csdn.net/renwotao2009/article/details/53039068
[WIKI]: https://zh.wikipedia.org/wiki/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84
[https_blog.csdn.net_xwchao2014_article_details_47754613]: https://blog.csdn.net/xwchao2014/article/details/47754613