Find consecutive repeated string - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Find consecutive repeated string

Find consecutive repeated string# JobHunting - 待字闺中

a*y2012-08-20 07:08

1 楼

Write a program which returns true if the given string contains the
consecutive repeated substring .Ex-adabcabcd
here abc is consecutive repeated substring.
这个我想要是用map来存character 的index的话，这个不好弄，因为你遇到duplicate
的时候，你不知道是应该update这个index还是不update这个index，因为后面有可能是
从第一个字母开始也有可能从第一次重复的时候开始
另外可以expand around center来进行，但是这就变成0（n^3)了，有啥好方法没有？

b*d2012-08-20 07:08

2 楼

duplicate
可以用修改后的suffix tree么？build suffix是linear time，虽然那个算法非常复杂
，很难一下写出来。但是其上每个node的path（从根开始的path）都是一个substring
。把每个node设计成
node {
char c；
List startPos；// 记录下这个node的从根到该node的path的起始点在原
string的位置。是个list因为可能有很多个这种string。
int pathLen; // 记录下这个node的从根到该弄得的path的长度,即该substring的
length。
}
build suffix tree的时候，如果add node时候，发现该node已经存在，说明该
substring已经存在，如果存在一个startPos + pathLen == curStartPos,说明存在一
个连续repeated的substring。
应该是linear time

【在 a*******y 的大作中提到】

: Write a program which returns true if the given string contains the
: consecutive repeated substring .Ex-adabcabcd
: here abc is consecutive repeated substring.
: 这个我想要是用map来存character 的index的话，这个不好弄，因为你遇到duplicate
: 的时候，你不知道是应该update这个index还是不update这个index，因为后面有可能是
: 从第一个字母开始也有可能从第一次重复的时候开始
: 另外可以expand around center来进行，但是这就变成0（n^3)了，有啥好方法没有？

a*y2012-08-20 07:08

3 楼

这个你怎么写build suffix tree的code？不可能当场完成吧，我觉得还得有另外个方
法来写code

b*d2012-08-20 07:08

4 楼

写N^2的方法来build suffix tree应该不是很难？

【在 a*******y 的大作中提到】

: 这个你怎么写build suffix tree的code？不可能当场完成吧，我觉得还得有另外个方
: 法来写code

a*y2012-08-20 07:08

5 楼

我就在想有没有更好的办法出了用sufix tree
写了个傻的，不过觉得有更好的
bool strMatch(char* str, int start, int length)
{
for (int i = 0; i {
if (str[start+i] != str[start-length+i])
return false;
}
return true;
}
bool ReturnConsecutiveString(char* str, int n, int& startindex, int&
endindex)
{
int i = 1, j,k;
bool bfail = false;
while (i < n)
{
for (j = 1; (i+j < n) && (i-j-1 >=0);j++)
{
for (k = 0; k<=j;k++)
{
if (strMatch(str, i, k+1))
{
startindex = i;
endindex = i+k;
return true;
}
}

}
i++;
}

return false;
}

a*y2012-08-20 07:08

6 楼

ok， I got it
use a suffix array, then sort it( remember index when you sort), now
repeated substring must occur in neigbor, compare two by two to find two
they have common prefix, and if the common prefix length equal to their
index difference +1 , that would be the answer