吧内搜索搜贴搜人进吧搜标签

扫二维码下载贴吧客户端

String專题又出现啦~(≧▽≦)/~ 这次的题很水的啦0.0

一个字符串的子串是该字符串的一段连续子序列如bca是abcabc的子串，而cc不是一个重复块(repeating block)由一个字符串与自身連接而成，如abcabc是一个重复块而abcabd, ababab不是。

你有┅个由拉丁字符组成的字符串每一步你要找到它的子串中最短的重复块，如果有多于一个你必须选择最左边的那个。你要将那个形如XX(X - 某个字符串)的重复块替换成X换句话说你要删除其中的一个X。重复以上步骤直到字符串中不存在重复块

最终的字符串会是怎样的？看样例解释来更清楚地理解问题描述

对于这道题我们考虑用hash来判断两个子串是否相同。所以我们先枚举重复串的长度i显然，若两個长度为i的重复串放在一起他们肯定会经过（k*i,(k+1) *i）的最长公共前缀和最长公共后缀，若最长公共前缀加最长公共后缀大于当前的i则说明這里可以构成一个长度为i的重复串，那么就重新从1到n区模拟判断删去重复串由于字符串缩减得很快，所以总复杂度为O(Nlog2N)