最近在一次亚马逊面试中，我被问到了这个问题。
给定一个字符串，从中删除连续重复的子串。如果有多个连续交叉的子串，则删除其中最大的一个。
为了清楚起见，以下是一些示例：
aabcccddeaaaabcdea（压缩连续重复字符）abababcdeeeabcde（压缩连续重复的子串）ababcdabcdababcd（您可以压缩“ab”或“abcd”，但由于“abcd”的长度更长，因此您更喜欢压缩较大的那个。）
我无法想出有效的实现方法，有人知道一个好的方法吗？
由于这是一道面试题，请不要使用复杂的库函数。
X，我们可以使用 Z算法 在O(n^2)的时间复杂度内找到最长连续重复子串。该算法会生成一个数组Z，其中Z[i]表示从pat[i]开始的最长子串的长度，该子串也是pat的前缀(来源)。i为起始位置的后缀，应用Z算法来计算其最长连续重复子串。int result = 0;
for(int i = 0; i < X.length(); i++)
int[]z = Z-algo(X.substring(i)); //this take O(n)
for(int j = i + result + 1; j < X.length(); j++)
if(z[j] >= j - i + 1)
result = (j - i + 1);
重复上述过程，直到我们找不到任何重复的子字符串，我们就可以得到一个O(n^3)的算法。
注意：在重新阅读问题，特别是最后一个示例之后，我发现有效的重复子字符串仅限于原始子字符串。因此，可以通过使用最大堆将时间复杂度降低到O(n^2 log n)。
pos=[]
dstr={}
final=[]
x="ababcdabcdcde"
for k in re.finditer(r"(?=(.+?)\1+)",x): #Find start of all overlapping strings
pos.append(k.start())
i=0
for k in pos: #Find end of overlapping strings
s=re.findall(r"^((.*)\2+)",x[k:])
dstr[i]=(k,len(s[0][0]))
i=i+1
#print dstr.values()
k=0
while k< len(dstr.values())-1: #remove smaller length overlapping result
if dstr.values()[k+1][0]<dstr.values()[k][1]<dstr.values()[k+1][1]:
pass
else:
final.append(dstr.values()[k][0])
k=k+1
if dstr.values()[k-1][0] in final:
pass
else:
final.append(dstr.values()[k][0])
#print final
for k in final: #remove strings
s=re.sub(r"(.*)\1+",r"\1",x[k:])
x=x[:k]+s
print x
这是Python代码。在给定的输入下可以正常工作。
var cases = ['aabcccddeaaa', 'abababcdeee', 'ababcdabcd'];
function compress(str) {
var len, sub, i, n;
// if str is shorter than 2, can't be any repeating substrings
if(str.length < 2)
return str;
// max meaningful length is str.length/2 (truncated to integer)
for(len = (str.length / 2) | 0; len > 0; len--) {
// search for a repeating substring of "len" length starting at index i
for(i = 0; i + (len * 2) <= str.length; i++) {
sub = str.substr(i, len);
// if such a substring exists...
if(str.indexOf(sub, i + len) == i + len) {
// "count" how many occurences (advance index till beyond repeats)
for(n = i + len * 2; str.indexOf(sub, n) == n; n += len);
// return a string composed of the compressed part before the match +
// the substring + the compressed part beyond the match
return compress(str.substr(0, i)) + sub + compress(str.substr(n));
}
}
}
// if nothing found, return original string
return str;
}
alert(JSON.stringify(cases.map(compress)));在评论区讨论了算法复杂度的问题后，我决定进行一些重构，并使用自己实现的startsWith函数来计算内部操作（复杂度...）。
我抓住机会进一步优化，将字符串分配最小化，因此递归使用整个字符串+起始/结束索引。
下面的代码生成一个输出，其中包括输入字符串、结果、n^2（用于O(n^2)比较）和实际内部操作计数。我添加了一些边缘情况以展示其性能。我找不到导致n^2计数的输入，它们都在以下范围内。
var cases = ['aabcccddeaaa', 'abababcdeee', 'ababcdabcd',
'aabaaabaab', '1', '111222', '123456789', '1234567899'];
var innerCount;
function startsWith(str, start, subStart, subLen) {
var subEnd = subStart + subLen - 1;
while(subStart <= subEnd) {
innerCount++;
if(str[start++] != str[subStart++])
return false;
}
return true;
}
function doCompress(str, maxLen, minIndex, maxIndex) {
var len, sub, i, n;
// if str is shorter than 2, can't be any repeating substrings
if(maxIndex - minIndex + 1 < 2)
return str.substring(minIndex, maxIndex + 1);
for(len = maxLen; len > 0; len--) {
// search for a repeating substring of "len" length starting at index i
for(i = minIndex; i + (len * 2) <= maxIndex + 1; i++) {
// if such a substring exists...
if(startsWith(str, i + len, i, len)) {
// "count" how many occurences (advance index till beyond repeats)
for(n = i + len * 2; (n + len <= maxIndex + 1) && startsWith(str, n, i, len); n += len);
// return a string composed of the compressed part before the match +
// the substring + the compressed part beyond the match
return (i > minIndex ? doCompress(str, len - 1, minIndex, i - 1) : '') +
str.substr(i, len) +
(n < maxIndex ? doCompress(str, len, n, maxIndex) : '');
}
}
}
// if nothing found, return original string
return str.substring(minIndex, maxIndex + 1);
}
function compress(str) {
innerCount = 0;
// max meaningful length is str.length/2 (truncated to integer)
return {
source: str,
result: doCompress(str, (str.length / 2) | 0, 0, str.length - 1),
'n^2': str.length*str.length,
innerCount: innerCount};
}
alert(JSON.stringify(cases.map(compress), null, '\t'));有一种简单的非递归O(n^3)方法。关键观察是：假设有一个字符串'aabcbcabbc'，如果我们只删除连续重复，只要我们先减少长度为1的字符串，其次是长度为2的字符串，以此类推，我们就可以将其缩小，而且缩小是最优的。因此
'aabcabbc' => 'abcbcabc' => 'abcabc' => 'abc'
Python代码：
def strcompress(str):
strlen = len(str)
for size in range (1, strlen // 2):
for i in range (0, strlen - 2 * size + 1):
str1 = str[i:i+size]
str2 = str[i+size:i+2*size]
while str1 == str2:
str = str[:i+size] + str[i+2*size:]
strlen = len(str)
if i + 2*size > strlen:
break
str2 = str[i+size:i+2*size]
print("The compressed string is:" + str)
return
例子：
>>> strcompress("ababcdabcd")
The compressed string is:abcd
编辑：修复了代码中的一些错误。这应该适用于现有样本和我提供的示例。
ababcdabcd，输出为 ababcd。 - Amit