[ZOJ3199 Longest Repeated Substring]【后缀数组】【枚举答案】

【题目链接】http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3324

【题目大意】

给定一个串,让你求里面的最长连续重复子串的长度。

这个连续重复子串是这么定义的:

设S为原串Str里的一个子串,如果在Str里,S后面紧接着一个和S一模一样的串,那么S被称为连续重复子串。

【算法分析】

枚举答案ans,对原串的n/ans个字符进行标记,每个字符之间间隔ans-1个字符。

那么假如答案ans成立,那么对应长度为ans的连续重复子串必然包含且仅包含一个被标记的字符。

然后他紧接着和他一模一样的字符串必然会包含且仅包含下一个被标记的字符。

于是令现在其中一个标记为i,我们只需要求(i,i+ans)之间的最长公共前缀和最长公共后缀就可以了。

最长公共前缀和最长公共后缀可以通过建立一个正向字符串的后缀数组和一个逆向字符串的后缀数组来实现。

【时间复杂度】O(n lg n)  【n/1+n/2+n/3+...+n/n <= n lg n】

【空间复杂度】O(n lg n)

【CODE】http://xiudaima.appspot.com/code/detail/4293043

加入对话

1条评论

留下评论

您的电子邮箱地址不会被公开。