寻找一个字符串中的最长重复子串（后缀数组）以及　找出一个字符串中最长不重复子串

绝地灬酷狼 2022-03-26 11:10 254阅读 0赞

### 一、寻找一个字符串中的最长重复子串（后缀数组） ###

后缀数组其实可以看寻找一个字符串中的最长重复子串（后缀数组）作一个由字符串s倒数i个字符组成的子串的集合，其中`0<i<s.length()`，例如 字符串`strstr`的后缀数组为：   
`{r,tr,str,rstr,trstr,strstr}`   
得到这个集合之后，我们可以发现，最长重复子串其实变成了**求该集合中任意两个元素的最长公共前缀**的问题。因为在这个集合中，原字符串中的每个字符都会出现在集合中元素的首位，而如果有子串重复出现，那么该子串肯定会出现在某两个或者多个元素的公共前缀上。   
接下来问题就变成了如何去寻找最长公共前缀，除了暴力搜素之外，我们可以考虑先对该集合中的元素按照字典序进行排序，然后依次比较相邻的元素，找出其中的最长公共前缀即可。

[https://dsqiu.iteye.com/blog/1701324][https_dsqiu.iteye.com_blog_1701324]

[https://blog.csdn.net/kongdavid/article/details/38405475][https_blog.csdn.net_kongdavid_article_details_38405475]

[https://blog.csdn.net/htq\_\_/article/details/50855769][https_blog.csdn.net_htq_article_details_50855769]

### 二、找出一个字符串中最长不重复子串（python） ###

[https://blog.csdn.net/together\_cz/article/details/77533121][https_blog.csdn.net_together_cz_article_details_77533121]

[https_dsqiu.iteye.com_blog_1701324]: https://dsqiu.iteye.com/blog/1701324
[https_blog.csdn.net_kongdavid_article_details_38405475]: https://blog.csdn.net/kongdavid/article/details/38405475
[https_blog.csdn.net_htq_article_details_50855769]: https://blog.csdn.net/htq__/article/details/50855769
[https_blog.csdn.net_together_cz_article_details_77533121]: https://blog.csdn.net/together_cz/article/details/77533121