求一个字符串的最大重复子串

题目描述

对于任意一个输入字符串s,我们被要求确定其最大的递归子串及其出现次数。例如，在'banana'这一特定案例中,递归子串'ana'被识别为最长的那个。

问题分析

题目要求寻找最长的重复子串.“最长"和"重复"是关键.既然是最长,根据我们的编程经验,必然需要一个变量用以保存这个最长的子串,并且这个变量在遍历比较中不断地被更新.那么比较又怎么来的?如何比较?这里我们看"重复”,既然是重复,代表出现两次以上,所以一个字符子串只要出现两次就有可能被我们选为答案.那么很明显,这样的字符子串就是我们的比较对象,而比较的,正是它们的长度.对于算法而言,一个难点就是,**应当如何开始,如何不遗漏地遍历到所有的情况,以一个怎样的顺序进行?**这是一个算法能否实现的核心.一个复杂问题的经典算法必然伴随着一个巧妙的解决思路,就拿这个问题来说.我们就把问题转换成了找这个字符串是否有两个最长的相同子串,根据这个想法,我们可以有一个朴素(暴力)的算法,找到这个字符串的最长子串(设这个字符串长度为n,那么就从n-1开始),找这个字符串有没有其他这样的子串,比如说一个字符串有两个n-1长度的子串,那么就比较它们是否相等就可以了.如果不相等,那么就找长度为n-2的子串,再寻找有没有其他长度为n-2的子串与这个子串相等.这个寻找方式可以这么进行:首先从头开始截取长度为n-2的子串,再从第