m**q
发帖数: 189 | 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**********y
发帖数: 14569 | 2 字符串长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;
}
【在 m**q 的大作中提到】
: 考古到一道老题：
: 给个string,判断这个string是否是某个pattern的周期循环
: （这个pattern不确定）要nlgn复杂度 我给了算法 ，
: 不能cover所有情况，提醒后，给了正确算法，然后code,没错
: 我的思路是用suffix array，创建后sort，然后在sorted array中
: 比较相邻的元素，如果前面的字符串长度小于后面，则后面的字符串
: 应该包含前面的，且两个字符串的差就是循环的pattern - 如果对于
: 所有的相邻元素都成立，则可以确定原string是这个pattern的循环
: 大家看看有更好的思路么
: abcdabcd:
|
d*******d
发帖数: 2050 | 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******3
发帖数: 351 | 4 assume s = word.substring(0, i)
examine whether the string "("+s+")" matches pattern or not. ^ indicates
beginning of a string, $-ending. |
d*******d
发帖数: 2050 | 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**********y
发帖数: 14569 | 6 见hunter33解释，就是看string是不是pattern的重复，这个是O(n)的操作，自己写实
现也很简单。
【在 d*******d 的大作中提到】
: 不懂java,能不能解释一下这句话.
: Pattern.matches("^(" + word.substring(0, i) + ")*$", word)
|
g**********y
发帖数: 14569 | 7 是
【在 d*******d 的大作中提到】
: *表示括号里的s出现0次或多次,是吧.
|
c****7
发帖数: 4192 | 8 牛啊
【在 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******3
发帖数: 351 | 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*********l
发帖数: 2005 | 10 解法正确，但复杂度不对吧？
这个循环外围是O(n),Pattern.matches() 本身也是O(n)的吧？
单就这个Pattern.matches("^(pattern)*$", word) 来说，你不把这个字符串过一遍，
你没法知道这个字符串是不是pattern重复N遍吧？
【在 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;
: }
|
|
|
g**********y
发帖数: 14569 | 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*****s
发帖数: 95 | 12 t 次就行. if it repeats, it has to repeat p_1, ..., or p_t times. |
m**q
发帖数: 189 | 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*****s
发帖数: 95 | 14 (k1+1)...(kt+1) can certainly be more than log N. but t is not. |
b***e
发帖数: 1419 | 15 貌似判最长的自相交O(n)可以搞定。用suffix tree.
【在 m**q 的大作中提到】
: 考古到一道老题：
: 给个string,判断这个string是否是某个pattern的周期循环
: （这个pattern不确定）要nlgn复杂度 我给了算法 ，
: 不能cover所有情况，提醒后，给了正确算法，然后code,没错
: 我的思路是用suffix array，创建后sort，然后在sorted array中
: 比较相邻的元素，如果前面的字符串长度小于后面，则后面的字符串
: 应该包含前面的，且两个字符串的差就是循环的pattern - 如果对于
: 所有的相邻元素都成立，则可以确定原string是这个pattern的循环
: 大家看看有更好的思路么
: abcdabcd:
|
m**q
发帖数: 189 | 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**********y
发帖数: 14569 | 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*****s
发帖数: 95 | 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**q
发帖数: 189 | 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).
|
