判断一个string是否是某个pattern的周期循环 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

判断一个string是否是某个pattern的周期循环

判断一个string是否是某个pattern的周期循环# JobHunting - 待字闺中

m*q2011-09-16 07:09

1 楼

考古到一道老题：
给个string,判断这个string是否是某个pattern的周期循环
（这个pattern不确定）要nlgn复杂度我给了算法，
不能cover所有情况，提醒后，给了正确算法，然后code,没错
我的思路是用suffix array，创建后sort，然后在sorted array中
比较相邻的元素，如果前面的字符串长度小于后面，则后面的字符串
应该包含前面的，且两个字符串的差就是循环的pattern - 如果对于
所有的相邻元素都成立，则可以确定原string是这个pattern的循环
大家看看有更好的思路么
abcdabcd:
abcdabcd abcd
bcdabcd abcdabcd
cdabcd bcd
dabcd --> bcdabcd
abcd cd
bcd cdabcd
cd d
d dabcd
ababab:
ababab ab
babab abab
abab --> ababab
bab b
ab bab
b babab
aabaab:
aabaab aab
abaab aabaab
baab --> ab
aab abaab
ab b
b baab

g*y2011-09-16 07:09

2 楼

字符串长N, 对N的所有小于N的因数搜索，这个就是N*log(N)的。
public boolean isRepeated(String word) {
int N = word.length();
for (int i=1; iif (N%i == 0 &&
Pattern.matches("^(" + word.substring(0, i) + ")*$", word))
return true;
}
return false;
}

【在 m**q 的大作中提到】

: 考古到一道老题：
: 给个string,判断这个string是否是某个pattern的周期循环
: （这个pattern不确定）要nlgn复杂度我给了算法，
: 不能cover所有情况，提醒后，给了正确算法，然后code,没错
: 我的思路是用suffix array，创建后sort，然后在sorted array中
: 比较相邻的元素，如果前面的字符串长度小于后面，则后面的字符串
: 应该包含前面的，且两个字符串的差就是循环的pattern - 如果对于
: 所有的相邻元素都成立，则可以确定原string是这个pattern的循环
: 大家看看有更好的思路么
: abcdabcd:

d*d2011-09-16 07:09

3 楼

不懂java,能不能解释一下这句话.
Pattern.matches("^(" + word.substring(0, i) + ")*$", word)

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

: 字符串长N, 对N的所有小于N的因数搜索，这个就是N*log(N)的。
: public boolean isRepeated(String word) {
: int N = word.length();
: for (int i=1; i: if (N%i == 0 &&
: Pattern.matches("^(" + word.substring(0, i) + ")*$", word))
: return true;
: }
: return false;
: }

h*32011-09-16 07:09

4 楼

assume s = word.substring(0, i)
examine whether the string "("+s+")" matches pattern or not. ^ indicates
beginning of a string, $-ending.

d*d2011-09-16 07:09

5 楼

*表示括号里的s出现0次或多次,是吧.

【在 h******3 的大作中提到】

: assume s = word.substring(0, i)
: examine whether the string "("+s+")" matches pattern or not. ^ indicates
: beginning of a string, $-ending.

g*y2011-09-16 07:09

6 楼

见hunter33解释，就是看string是不是pattern的重复，这个是O(n)的操作，自己写实
现也很简单。

【在 d*******d 的大作中提到】

: 不懂java,能不能解释一下这句话.
: Pattern.matches("^(" + word.substring(0, i) + ")*$", word)

g*y2011-09-16 07:09

7 楼

是

【在 d*******d 的大作中提到】

: *表示括号里的s出现0次或多次,是吧.

c*72011-09-16 07:09

8 楼

牛啊

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

h*32011-09-16 07:09

9 楼

I understand one of the reasons that the code can be concise is:
whether the string includes repeated pattern. That's why we care about the
factor of N. And the running time is Nlog(N).

【在 c****7 的大作中提到】

: 牛啊

A*l2011-09-16 07:09

10 楼

解法正确，但复杂度不对吧？
这个循环外围是O(n),Pattern.matches() 本身也是O(n)的吧？
单就这个Pattern.matches("^(pattern)*$", word) 来说，你不把这个字符串过一遍，
你没法知道这个字符串是不是pattern重复N遍吧？

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

g*y2011-09-16 07:09

11 楼

N = p1^k1 * p2^k2 ... pt^kt
then N has (k1+1)*(k2+1)*...*(kt+1) factors, that's O(logN)

【在 A*********l 的大作中提到】

: 解法正确，但复杂度不对吧？
: 这个循环外围是O(n),Pattern.matches() 本身也是O(n)的吧？
: 单就这个Pattern.matches("^(pattern)*$", word) 来说，你不把这个字符串过一遍，
: 你没法知道这个字符串是不是pattern重复N遍吧？

f*s2011-09-16 07:09

12 楼

t 次就行. if it repeats, it has to repeat p_1, ..., or p_t times.

m*q2011-09-16 07:09

13 楼

N包含的因子数可以用归纳法算出来，但是怎么证明这个是O(logN)的呢？

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

: N = p1^k1 * p2^k2 ... pt^kt
: then N has (k1+1)*(k2+1)*...*(kt+1) factors, that's O(logN)

f*s2011-09-16 07:09

14 楼

(k1+1)...(kt+1) can certainly be more than log N. but t is not.

b*e2011-09-16 07:09

15 楼

貌似判最长的自相交O(n)可以搞定。用suffix tree.

【在 m**q 的大作中提到】

m*q2011-09-16 07:09

16 楼

Right t is no more than O(lgn)
But we still need to walk through all these
(k1+1)(k2+1)...(kt+1) numbers, so seems the complexity
for this is not going to be O(nlgn) with this method...

【在 f*****s 的大作中提到】

: (k1+1)...(kt+1) can certainly be more than log N. but t is not.

g*y2011-09-16 07:09

17 楼

用筛法算素数，只需要判断所有的N/p, p是素数。
public boolean isRepeated(String word) {
int N = word.length();
boolean[] composite = new boolean[N+1];
for (int i=2; i<=N; i++) {
if (!composite[i]) {
if (N%i == 0 &&
Pattern.matches("^(" + word.substring(0, N/i) + ")*$", word)
) return true;
for (int j=i*2; j<=N; j+=i) composite[j] = true;
}
}
return false;
}

【在 m**q 的大作中提到】

: Right t is no more than O(lgn)
: But we still need to walk through all these
: (k1+1)(k2+1)...(kt+1) numbers, so seems the complexity
: for this is not going to be O(nlgn) with this method...

f*s2011-09-16 07:09

18 楼

If S is periodic, then it has to consist of p_i identical substrings for
some 1<=i<=t. This is not an algorithm question. It is about number theory.
Sieving takes N loglog N. Naive division takes Sqrt(N).

m*q2011-09-16 07:09

19 楼

明白了
谢谢火鸡和fantans

.

【在 f*****s 的大作中提到】

: If S is periodic, then it has to consist of p_i identical substrings for
: some 1<=i<=t. This is not an algorithm question. It is about number theory.
: Sieving takes N loglog N. Naive division takes Sqrt(N).