由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 我也发一道A家的电面题,不难,但是跪了。。。。
相关主题
还真从来没见过考KMP之类string matching算法的Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
storm8 online test 讨论FB面试题一道 求解
问一道n-ary tree 的题目F面经的一题
求教电面遇到的一道pattern match的实现没啥乐趣了
我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印问一个KMP算法的问题
问一个Pinterest的题目微软电面
问个google老题的最佳解法问2道面试题
G onsite题求讨论查找substr的问题
相关话题的讨论汇总
话题: string话题: int话题: false话题: return话题: len
进入JobHunting版参与讨论
1 (共1页)
m*********1
发帖数: 204
1
有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
2,输入一个String写代码返回T或者F
例子:
"abcabcabc" Ture 因为它把abc重复3次构成
"bcdbcdbcde" False 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" False 因为它不是某一个String重复
"aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
要求算法复杂度为O(n)
public boolean isMultiple(String s){
}
一紧张,大脑一片空白,直接不会做!!!
p*****2
发帖数: 21240
2
KMP吧。
f*****e
发帖数: 2992
3
确实,太牛了。

【在 p*****2 的大作中提到】
: KMP吧。
A*********c
发帖数: 430
4
build and check suffix tree.

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

z******h
发帖数: 22
5
直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
符串的开头必然是pattern的开头,并没有必要KMP。

★ 发自iPhone App: ChineseWeb 7.8
★ 发自iPhone App: ChineseWeb 7.8

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

w*******i
发帖数: 186
6
是的,先找第一个字符重复出现的地方,找到后假设这个字符与第一个字符间就是重复
的短字符串。然后继续扫描逐字匹配,不对就更新假设的重复的短字符串。
最后验证这个重复的短字符串长度是否够大。

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

z***g
发帖数: 51
7
Good idea!但是怎么保证greedy就是最优呢?可能是我理解有问题,我怎么觉得9个a的
case greedy方法过不了。pattern=2 开始aaaaaaaaa这样一直找,知道最后才不行,也
就是第八个a,更新以后就是pattern=8了,这样找不出来。但是aaa,aaa,aaa pattern=
3是可分的。

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

l*****r
发帖数: 2122
8
反过来想,原string长度依次除以质数,从小到大。(2,3,5,7,11。。)
能整除的话,接着看是否匹配,不能的话看下一个稍大的质数。直到质数>n/2。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

l******t
发帖数: 37
9
In Python:
def isMultiple(string):
if not string:
return
step = 2
repeatstring = None
while step < len(string):
pat = string[:step]
if len(string) % len(pat) == 0:
if pat*(len(string)/len(pat)) == string:
if not repeatstring:
repeatstring = pat
step += 1
if repeatstring:
print 'repeatstring:', repeatstring
return len(set(repeatstring)) != 1
else:
return False
r*****e
发帖数: 30
10
public boolean isMultiple(String s){
if(s==null || s.length()<3) return false;
ArrayList pattern = new ArrayList();
pattern.add(s.charAt(0));
pattern.add(s.charAt(1));
int times = 1;
int pos = 0;
for(int i=2; i if(s.charAt(i)==pattern.get(pos)){
if(pos==pattern.size()-1){
times++;
pos = 0;
}
else{
pos++;
}
}
else{
for(int j=pattern.size(); j<=i; j++){
pattern.add(s.charAt(j));
}
times = 1;
pos = 0;
}
}
if(times==1 || pos!=0) return false;
boolean isSame = true;
for(int i=0; i if(pattern.get(i)!=pattern.get(0)){
isSame = false;
}
}
if(isSame) return false;
return true;
}
相关主题
问一个Pinterest的题目Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
问个google老题的最佳解法FB面试题一道 求解
G onsite题求讨论F面经的一题
进入JobHunting版参与讨论
z******h
发帖数: 22
11
没问题,pattern="a" forever
事实上9个a这个case让我确定这个方法应该是标准答案...

pattern=
★ 发自iPhone App: ChineseWeb 7.8

【在 z***g 的大作中提到】
: Good idea!但是怎么保证greedy就是最优呢?可能是我理解有问题,我怎么觉得9个a的
: case greedy方法过不了。pattern=2 开始aaaaaaaaa这样一直找,知道最后才不行,也
: 就是第八个a,更新以后就是pattern=8了,这样找不出来。但是aaa,aaa,aaa pattern=
: 3是可分的。
:
: pattern

m*****n
发帖数: 2152
12
"bcdbcdbcdebcdbcdbcde" 是true 还是false啊?

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

m*****n
发帖数: 2152
13
为什么啊,“bcdbcdbcdebcdbcdbcde”可以分成"bcdbcdbcde" x 2啊。而且10个a尽然
也是false,说"aa" x 5和 "aaaaa" x2都不算,不能理解啊。

【在 f*****e 的大作中提到】
: 确实,太牛了。
f*****e
发帖数: 2992
14
没看清楚,应该是true。

【在 m*****n 的大作中提到】
: 为什么啊,“bcdbcdbcdebcdbcdbcde”可以分成"bcdbcdbcde" x 2啊。而且10个a尽然
: 也是false,说"aa" x 5和 "aaaaa" x2都不算,不能理解啊。

A*********c
发帖数: 430
15
great idea!

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

l*****4
发帖数: 267
16
贡献一下我的,试过大家提到的所有case, 都可以
public boolean isMultiple(String s) {
if (s == null || s.length() == 0) {
return false;
}
int len = s.length();
if (len == 1) {
return true;
}
if (len == 2) {
return s.charAt(0) == s.charAt(1);
}
int left = 0;
for (int i = 1; i < len; i++) {
char c = s.charAt(i);
if (c == s.charAt(left)) {
left++;
} else {
left = 0;
}
}
if (len % 2 == 0) {
return left >= (s.length() / 2 - 1);
} else {
return left > (s.length() / 2);
}

}
x****g
发帖数: 1512
17
不理解。
ababcababc.
abaaba.
怎么都能成功呢?

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

j*****8
发帖数: 3635
18
那位兄台的算法针对abaaba过不去,做个小改动;如果发现不匹配当前pattern,就和
首字母比较一下;如果和首字母一样,pattern改成首字母到当前字母的前一位;否则
pattern改成首字母到当前字母

【在 x****g 的大作中提到】
: 不理解。
: ababcababc.
: abaaba.
: 怎么都能成功呢?
:
: pattern

z******h
发帖数: 22
19
恩我那个是有问题
你这个对于abaaaaaaba这样的怎么处理?好像还是要出问题。

【在 j*****8 的大作中提到】
: 那位兄台的算法针对abaaba过不去,做个小改动;如果发现不匹配当前pattern,就和
: 首字母比较一下;如果和首字母一样,pattern改成首字母到当前字母的前一位;否则
: pattern改成首字母到当前字母

j*****8
发帖数: 3635
20
没问题阿,这个返回false
整个字符串走完后,check pattern的长度,如果等于n,返回false

【在 z******h 的大作中提到】
: 恩我那个是有问题
: 你这个对于abaaaaaaba这样的怎么处理?好像还是要出问题。

相关主题
没啥乐趣了问2道面试题
问一个KMP算法的问题查找substr的问题
微软电面Longest common string问题
进入JobHunting版参与讨论
x****g
发帖数: 1512
21
我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
溯。
不证明这一点,这种修正都会引起反例。
比方说。
aaaba aaaba
你修改后也不行。
a引起失败在b,
所以变成aaab.
这次引起失败在aaabaaa[a]
你取不回aaaba了,呵呵。

【在 j*****8 的大作中提到】
: 那位兄台的算法针对abaaba过不去,做个小改动;如果发现不匹配当前pattern,就和
: 首字母比较一下;如果和首字母一样,pattern改成首字母到当前字母的前一位;否则
: pattern改成首字母到当前字母

z******h
发帖数: 22
22
的确是,看来这条路有问题。
刚才找了半天反例没找到,被你发现了...

【在 x****g 的大作中提到】
: 我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
: 溯。
: 不证明这一点,这种修正都会引起反例。
: 比方说。
: aaaba aaaba
: 你修改后也不行。
: a引起失败在b,
: 所以变成aaab.
: 这次引起失败在aaabaaa[a]
: 你取不回aaaba了,呵呵。

b****f
发帖数: 138
23
Passed Test Run, Not sure if having other bugs
class Solution {
public:
bool isMultiple (string s){
int N=s.size();
if(N<3) return false;
int len=1;
int start=0;
for(int i=1;i if(s[start]==s[i]){
start++;
if(start>=len) start=0;
}
else{
len=i+1;
start=0;
}
if(len>N/2) return false;
}
return len!=1;
}
};
void main() {
Solution sol;
cout< cout< cout< cout< cout< _getch();
}
x****g
发帖数: 1512
24
你这个长度增加1,但i不回溯?
感觉你pass不过我的case ? 呵呵。
aaaba aaaba
先讲原理后写代码比较好。

【在 b****f 的大作中提到】
: Passed Test Run, Not sure if having other bugs
: class Solution {
: public:
: bool isMultiple (string s){
: int N=s.size();
: if(N<3) return false;
: int len=1;
: int start=0;
: for(int i=1;i: if(s[start]==s[i]){

z******h
发帖数: 22
25

~~~~~~~~~~~~~~~~~~~~Re

【在 x****g 的大作中提到】
: 你这个长度增加1,但i不回溯?
: 感觉你pass不过我的case ? 呵呵。
: aaaba aaaba
: 先讲原理后写代码比较好。

j*****8
发帖数: 3635
26
有道理。。

【在 x****g 的大作中提到】
: 我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
: 溯。
: 不证明这一点,这种修正都会引起反例。
: 比方说。
: aaaba aaaba
: 你修改后也不行。
: a引起失败在b,
: 所以变成aaab.
: 这次引起失败在aaabaaa[a]
: 你取不回aaaba了,呵呵。

b****f
发帖数: 138
27
前面的评论没看,i不回溯的确过不了,这个暴力法都可以过,但貌似超时了,感觉现
在只能用KMP了
class Solution {
public:
bool isMultiple (string s){
int N=s.size();
if(N<3) return false;
int len=1;
int start=0;
for(int i=1;i if(s[start]==s[i]){
start++;
if(start>=len) start=0;
}
else{
len++;
i=len-1;
start=0;
}
if(len>N/2) return false;
}
return len!=1;
}
};
void main() {
Solution sol;
cout< cout< cout< cout< cout< cout< cout< _getch();
}
s******t
发帖数: 229
28
abaabaaba
怎么扫?

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

k****s
发帖数: 16
29
这个思路非常好。
问题应该只出现在真实pattern的prefix和suffix相同。
1. prefix和suffix相同且不为同一字母,之前方法(直接看到从前)可解。
2. prefix和suffix相同且为同一字母,这就必须得Pattern+1了。
所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题,
那么Pattern+1, 否则就 直接看到从前。
比如 aba aba 失败在第三个a 应该match的是b,所以pattern+1
aaaba aaaba最后失败在aaabaaa[a],应该match的是b,所以pattern+1.
更新完pattern后,只需要把当前match的b前移一位match,来保证O(n)

【在 x****g 的大作中提到】
: 我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
: 溯。
: 不证明这一点,这种修正都会引起反例。
: 比方说。
: aaaba aaaba
: 你修改后也不行。
: a引起失败在b,
: 所以变成aaab.
: 这次引起失败在aaabaaa[a]
: 你取不回aaaba了,呵呵。

s******d
发帖数: 424
30
你这得扫多少次?O(N)不可能啊

【在 l******t 的大作中提到】
: In Python:
: def isMultiple(string):
: if not string:
: return
: step = 2
: repeatstring = None
: while step < len(string):
: pat = string[:step]
: if len(string) % len(pat) == 0:
: if pat*(len(string)/len(pat)) == string:

相关主题
问几道较难的字符串题storm8 online test 讨论
finds all repeated substrings in the string --- YAHOO interview question问一道n-ary tree 的题目
还真从来没见过考KMP之类string matching算法的求教电面遇到的一道pattern match的实现
进入JobHunting版参与讨论
s******t
发帖数: 229
31

目前还没想到什么反例。。。想到反例估计又要fix bug

【在 k****s 的大作中提到】
: 这个思路非常好。
: 问题应该只出现在真实pattern的prefix和suffix相同。
: 1. prefix和suffix相同且不为同一字母,之前方法(直接看到从前)可解。
: 2. prefix和suffix相同且为同一字母,这就必须得Pattern+1了。
: 所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题,
: 那么Pattern+1, 否则就 直接看到从前。
: 比如 aba aba 失败在第三个a 应该match的是b,所以pattern+1
: aaaba aaaba最后失败在aaabaaa[a],应该match的是b,所以pattern+1.
: 更新完pattern后,只需要把当前match的b前移一位match,来保证O(n)

H*********a
发帖数: 34
32
我也发一个想法,从string的第2位开始扫(为了保证那个子string的长度为2),当前
位的char和string首char一样的时候,就以首位到当前位的子string为模型,匹配后面
的相隔同等位置,同等长度的子string。这个方法不能处理"aaaaaaaaaa",因为认为这
是"aaaaa"乘以2。
bool check(int l, int n, string s) {
if (n % l != 0)
return false;
for (int j = 1; j < n/l; j++) {
if (s.substr(0, l) != s.substr(j*l, l))
return false;
}
return true;
}
bool isMultiple(string s) {
int n = s.size();
if (n <= 3)
return false;
for (int i = 2; i <= n/2; i++) {
if (s[i] == s[0]) {
if (check(i, n, s))
return true;
}
}
return false;
}

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

s******d
发帖数: 424
33
一紧张确实容易的题也想不起来
看看这个版本有错误吗
bool isMultiple (string s){
int N = s.size();
if(N < 4) return false;
int start = 0;
int pattern_end = 0;
for(int i=1;i {
if(s[start] == s[i])
{
if(start == 0)
pattern_end = i - 1;
start++;
}
else
{
pattern_end = 0;
start=0;
if(s[0] == s[i])
{
start = 1;
pattern_end = i-1;
}
}
if(pattern_end >= N/2)
return false;
}
return pattern_end > 0 && (N % (pattern_end+1) == 0);
}
错的,还是需要回溯
s******d
发帖数: 424
34
beewmf的最后一个也有bug,考虑 abcabcabcab
下面是修改过的
bool isMultiple (string s){
int N=s.size();
if(N<4) return false;
int len=1;
int start=0;
for(int i=1;i if(s[start]==s[i]){
start++;
if(start>=len) start=0;
}
else{
len++;
i=len-1; // start from len
start=0;
}
if(len>N/2) return false;
}
return len!=1 && (N % len == 0);
}
M*******a
发帖数: 1633
35
这显然suffix tree么
x****g
发帖数: 1512
36
抱歉,没看懂。
1:为什么“应该”只出现在?
2:每次pattern变化都要判prefix & suffix? 这个不改变O(n)?
3: 为啥更新pattern+1之后,只需把当前前移一位,而不需要回溯?
另外有人提的KMP具体怎么做?我其实也挺质疑,哈哈。

【在 k****s 的大作中提到】
: 这个思路非常好。
: 问题应该只出现在真实pattern的prefix和suffix相同。
: 1. prefix和suffix相同且不为同一字母,之前方法(直接看到从前)可解。
: 2. prefix和suffix相同且为同一字母,这就必须得Pattern+1了。
: 所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题,
: 那么Pattern+1, 否则就 直接看到从前。
: 比如 aba aba 失败在第三个a 应该match的是b,所以pattern+1
: aaaba aaaba最后失败在aaabaaa[a],应该match的是b,所以pattern+1.
: 更新完pattern后,只需要把当前match的b前移一位match,来保证O(n)

s******d
发帖数: 424
37
suffix tree太复杂了,面试的时候能写出来吗
z*********e
发帖数: 10149
38
没看懂,为什么10个a是false?
为什么不能看成5个a重复2次或者2个a重复5次?
x****g
发帖数: 1512
39
假设s=S0...Sn-1
我觉得我会选择判定SkSk+1=[Sn-1][S0]位置出的k,
如果k+1能整除整体长度,那么S0...Sk就是当前的pattern,
比较成功的话就一直向前,
如果失败在某一处的话,那么pattern更新为到失败处之后的那个满足条件的k'.
需要思考细节,呵呵。
k****s
发帖数: 16
40

我描述有问题,不过那个方法确实也有问题,过不了 abaab abaab 。
我来再给个吧。
列出所有公因数,O(logn)。
pattern长度只能在公因数里,每次不match,增加pattern长度到公因数里的下一个。
再用kmp里的性质,来减少回溯。

【在 x****g 的大作中提到】
: 抱歉,没看懂。
: 1:为什么“应该”只出现在?
: 2:每次pattern变化都要判prefix & suffix? 这个不改变O(n)?
: 3: 为啥更新pattern+1之后,只需把当前前移一位,而不需要回溯?
: 另外有人提的KMP具体怎么做?我其实也挺质疑,哈哈。

相关主题
求教电面遇到的一道pattern match的实现问个google老题的最佳解法
我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印G onsite题求讨论
问一个Pinterest的题目Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
进入JobHunting版参与讨论
k****s
发帖数: 16
41

哦, 才看到,我说的是跟你这个一样吧。

【在 x****g 的大作中提到】
: 假设s=S0...Sn-1
: 我觉得我会选择判定SkSk+1=[Sn-1][S0]位置出的k,
: 如果k+1能整除整体长度,那么S0...Sk就是当前的pattern,
: 比较成功的话就一直向前,
: 如果失败在某一处的话,那么pattern更新为到失败处之后的那个满足条件的k'.
: 需要思考细节,呵呵。

z******h
发帖数: 22
42
这个前面有人说过了,而且应该不需要KMP因为不用回朔

★ 发自iPhone App: ChineseWeb 7.8

【在 k****s 的大作中提到】
:
: 哦, 才看到,我说的是跟你这个一样吧。

k****s
发帖数: 16
43

回溯还是要的吧。
比如
字符串 abaab abaab
当pattern 为aba
abaab abaab
第3个b不match
pattern 增到 abaab,要回溯到pattern+1位置开始匹配

【在 z******h 的大作中提到】
: 这个前面有人说过了,而且应该不需要KMP因为不用回朔
:
: ★ 发自iPhone App: ChineseWeb 7.8

a*******e
发帖数: 47
44
aaabbca aaabbca 何解?

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

w********s
发帖数: 1570
45
brute force多简单,复杂度 bool isPrefix(char* pattern, char* str, int size)
{
for (int i = 0; i < size && str[i] != '\0'; ++i)
{
if (str[i] != pattern[i])
return false;
}
return true;
}
int repeat(char* str)
{
int length = strlen(str);
int count = 0;
for (int i = 2; i <= length / 2; ++i)
{
if (length % i > 0)
continue;
count = 0;
int p = length / i;
for (int j = 1; j < p; ++j)
{
if (isPrefix(str, str + i * j, i))
count++;
else
{
count = 0;
break;
}
}
if (count > 0) return count + 1;
}
return 0;
}
M*******a
发帖数: 1633
46
人说了要O(n)

【在 w********s 的大作中提到】
: brute force多简单,复杂度: bool isPrefix(char* pattern, char* str, int size)
: {
: for (int i = 0; i < size && str[i] != '\0'; ++i)
: {
: if (str[i] != pattern[i])
: return false;
: }
: return true;
: }

x****g
发帖数: 1512
47
不行啊,坑爹的,呵呵.
长度分解也很重要?
举个例子来说,一个无比大的素数含了全相同的单个字符,要是纯字符串比,怎么也到不
了O(N).
有长度判定的话直接就false. 呵呵
x****g
发帖数: 1512
48
我想的不对啊,呵呵.
adb acb adb adb acb adb

【在 k****s 的大作中提到】
:
: 回溯还是要的吧。
: 比如
: 字符串 abaab abaab
: 当pattern 为aba
: abaab abaab
: 第3个b不match
: pattern 增到 abaab,要回溯到pattern+1位置开始匹配

s**x
发帖数: 7506
49

可以先统计所有字母的个数,取最小值。单一重复字母串就成了 is prime or not 了
。不过别的情况好像先统计帮助不大。

【在 x****g 的大作中提到】
: 不行啊,坑爹的,呵呵.
: 长度分解也很重要?
: 举个例子来说,一个无比大的素数含了全相同的单个字符,要是纯字符串比,怎么也到不
: 了O(N).
: 有长度判定的话直接就false. 呵呵

m********l
发帖数: 791
50
按照楼主给的test case
单一字符的话就直接return false了啊

【在 s**x 的大作中提到】
:
: 可以先统计所有字母的个数,取最小值。单一重复字母串就成了 is prime or not 了
: 。不过别的情况好像先统计帮助不大。

相关主题
FB面试题一道 求解问一个KMP算法的问题
F面经的一题微软电面
没啥乐趣了问2道面试题
进入JobHunting版参与讨论
m********l
发帖数: 791
51
找所有factors应该是O(sqrt(n))吧?

【在 k****s 的大作中提到】
:
: 回溯还是要的吧。
: 比如
: 字符串 abaab abaab
: 当pattern 为aba
: abaab abaab
: 第3个b不match
: pattern 增到 abaab,要回溯到pattern+1位置开始匹配

j**h
发帖数: 1230
52
写个笨的。
length = M * N * ... * Z: M, N, ..., Z are prime numbers.
从M到Z挨个试:
split input string into M parts, these M parts must be same.
w****y
发帖数: 56
53
is it the problem here?
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
A typical problem seen quite often is: given a string find its shortest
substring, such that the concatenation of one or more copies of it results
in the original string. Again the problem can be reduced to the properties
of the failure function. Let's consider the string
A B A B A B
and all its proper suffix/prefixes in descending order:
1 A B A B
2 A B
3 /the empty string/
Every such suffix/prefix uniquely defines a string, which after being "
inserted" in front of the given suffix/prefix gives the initial string. In
our case:
1 A B
2 A B A B
3 A B A B A B
Every such "augmenting" string is a potential "candidate" for a string, the
concatenation of several copies of which results in the initial string. This
follows from the fact that it is not only a prefix of the initial string
but also a prefix of the suffix/prefix it "augments". But that means that
now the suffix/prefix contains at least two copies of the "augmenting"
string as a prefix (since it's also a prefix of the initial string) and so
on. Of course if the suffix/prefix under question is long enough. In other
words, the length of a successful "candidate" must divide with no remainder
the length of the initial string.
So all we have to do in order to solve the given problem is to iterate
through all proper suffixes/prefixes of the initial string in descending
order. This is just what the "failure function" is designed for. We iterate
until we find an "augmenting" string of the desired length (its length
divides with no remainder the length of the initial string) or get to the
empty string, in which case the "augmenting" string that meets the above
requirement will be the initial string itself.
w********s
发帖数: 1570
54
建立每个字母的出现位置表,举个例子aaabbcaaaabbca
a:0,1,2,6,7,8,9,13
b:3,4,10,11
c:5,12
然后建立每个字母的可能
a:1,2,6,7
b:1,7
c:7
然后取重复出现的最小值:7
重复次数就是length/7
O(n)可以解决吧。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

w********s
发帖数: 1570
55
#include "stdafx.h"
#include
#include
#include
#include
typedef std::map> MyMap;
MyMap m;
int repeat2(char* str)
{
for (int i = 0; i < strlen(str); ++i)
{
char c = str[i];
if (m.find(c) == m.end())
{
std::vector v;
v.push_back(i);
m[c] = v;
}
else
{
m[c].push_back(i);
}
}
int* count = new int[strlen(str)];
memset(count, 0, strlen(str) * sizeof(int));
int nChars = 0;
for (MyMap::iterator it = m.begin(); it != m.end(); ++it)
{
char c = it->first;
std::vector v = it->second;
if (v.size() < 2) return 0;
for (int i = 1; i <= v.size() / 2; ++i)
{
int d = v[i] - v[0];
count[d]++;
}
nChars++;
}
for (int i = 0; i < strlen(str); ++i)
{
if (count[i] == nChars)
{
if (strlen(str) % i > 0 || i == 1)
return 0;
else
return strlen(str) / i;
}
}
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
char abc[] = "aaabbcaaaabbca";
std::cout << repeat2(abc);
getchar();
}
w********s
发帖数: 1570
56
以上所有测试都通过了,并且复杂度O(n)
m*********1
发帖数: 204
57
昨天晚上睡不着,上来发的,没想到一天有那么多回复了。看了大家的回复,我觉得我
这个题目不简单啊。呵呵。。。
不过这个题目我后来仔细思考过,我的做法是这样的:
1.两头同时开始扫,找到base case: 当substring(0,i) == substring(j,n)的时候,
我假设substring(0,i)为这个重复的base case. 这里n是原String的length
这里可以优化的是,如前面同学所说,i不能被length整除的话,就不用比较,直接跳
过去
2.从1找到base case以后,两头切掉,留下中间部分substring(i,j),先看一下长度,
能不能整除i,不能就直接false,可以的话,写个循环,每次切i长度下来,和base
case对比一下是不是相等,直到结束。
因为很多不能整除的数可以跳过去,这个做法的worse case 是长度正好是2^n的String
,并且base case正好是2^k的长度的情况。
比如 ababababababacab 这样找到base case = ab,然后要切到最后才发现ac,但是
感觉还是能满足O(n)
我贴下我的代码,如有错误请指正。另外,不知道KMP怎么写,知道的同学请指教。
public static boolean Repeat(String s){
int len = s.length();
if(len < 4)
return false;
for(int i=1;i<=len/2;i++){
if((len % i) == 0){
if(s.substring(0,i).equals(s.substring(len-i,len))){
String base = s.substring(0,i);
//Exclude all "a"s
int x = base.length()-1;
while(x > 0 && s.charAt(x) == s.charAt(x-1)){
x--;
}
if(x > 0){

if(len/2 == i){
return true;
}
else{
String tmp = s.substring(i,len-i);
if(tmp.length() % i != 0)
return false;
int k = tmp.length();
int t = tmp.length() - i;
while(t >= 0 && tmp.substring(t,k).equals(base) ){
t = t - i;
k = k - i;
}
if(k == 0)
return true;

}
}
}


}


}
return false;
}
m*********1
发帖数: 204
58
上面我说错了一个地方。
如果找出来的base case,后面切中间部分的时候发现不匹配,还要继续找下一个base
case,直到i = length/2 为止。 (我前面说return false,是不对的)
w********s
发帖数: 1570
59
你的优化不解决根本问题,我的算法比你简单多了

【在 m*********1 的大作中提到】
: 昨天晚上睡不着,上来发的,没想到一天有那么多回复了。看了大家的回复,我觉得我
: 这个题目不简单啊。呵呵。。。
: 不过这个题目我后来仔细思考过,我的做法是这样的:
: 1.两头同时开始扫,找到base case: 当substring(0,i) == substring(j,n)的时候,
: 我假设substring(0,i)为这个重复的base case. 这里n是原String的length
: 这里可以优化的是,如前面同学所说,i不能被length整除的话,就不用比较,直接跳
: 过去
: 2.从1找到base case以后,两头切掉,留下中间部分substring(i,j),先看一下长度,
: 能不能整除i,不能就直接false,可以的话,写个循环,每次切i长度下来,和base
: case对比一下是不是相等,直到结束。

m*********1
发帖数: 204
60
我没看明白你的算法
能不能再解释一下
取出位置以后的后面一步,位置的可能?

【在 w********s 的大作中提到】
: 你的优化不解决根本问题,我的算法比你简单多了
相关主题
查找substr的问题finds all repeated substrings in the string --- YAHOO interview question
Longest common string问题还真从来没见过考KMP之类string matching算法的
问几道较难的字符串题storm8 online test 讨论
进入JobHunting版参与讨论
w********s
发帖数: 1570
61
建立每个字母的出现位置表,举个例子aaabbcaaaabbca
a:0,1,2,6,7,8,9,13
b:3,4,10,11
c:5,12
然后建立每个字母的可能
a:1,2,6,7 (就是1-0, 2-0, 6-0, 7-0)
b:1,7
c:7
map[1] = 2次
map[2] = 1次
map[6] = 1次
map[7] = 3次
所以长度为7。元字符串长14, 14/7=2遍。

【在 m*********1 的大作中提到】
: 我没看明白你的算法
: 能不能再解释一下
: 取出位置以后的后面一步,位置的可能?

w********s
发帖数: 1570
62
想了一下,这个也有问题。
至今没有O(n)解。

【在 w********s 的大作中提到】
: 建立每个字母的出现位置表,举个例子aaabbcaaaabbca
: a:0,1,2,6,7,8,9,13
: b:3,4,10,11
: c:5,12
: 然后建立每个字母的可能
: a:1,2,6,7 (就是1-0, 2-0, 6-0, 7-0)
: b:1,7
: c:7
: map[1] = 2次
: map[2] = 1次

w********s
发帖数: 1570
63
素数的话,n以内有n/(ln(n)-1.08)个数,所以还是满足不了O(n)

【在 j**h 的大作中提到】
: 写个笨的。
: length = M * N * ... * Z: M, N, ..., Z are prime numbers.
: 从M到Z挨个试:
: split input string into M parts, these M parts must be same.

b**y
发帖数: 22
64
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::string;
int main(int argc, char* argv[])
{
cout<<"Please input a string"< string InputStr;
cin>>InputStr;
string subStr;
int i = InputStr.length()-1;
while(i>0)
{
subStr=InputStr.substr(i);
for(int j=i-1;j>=0;j--)
{
if(InputStr[j]!=subStr[(j%subStr.length())])
{
i=j;
break;
}
if(j==0)
{
//Done should be a true if size is bigger than 2 and less than half
if((subStr.size()>=2)&&(subStr.size() {
cout<<"Yes true"< return 0;
}
else
{
cout<<"No false"< return 0;
}

}
}
}
cout<<"No false"< return 0;
}
r*****t
发帖数: 68
65
my idea is to reassemble a string by moving certain number of chars from the
end to the head, and compare the new string with the old. if match, it
means the moved portion is the repeative portion. Can ignore the complexity
of string comparison?
int n=mInput.size()
if(n<=2)
return false;
string newstr(n, mInput[0]);//consist of unique char
if(mInput.compare(newstr)==0)
return false;
for i>=2 && i<=n/2)
{
if( (n-i)%i==0 )
{
//move last ith chars to the front
newstr=mInput.substr(n-i)+mInput.substr(0,n-i);
if(mInput.compare(newstr)==0)
return true;
}
return false;

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

m*****n
发帖数: 2152
66
有一个思路,
首先把字符串统计字符个数 O(1),比如,
“abaabaabac”
就是6个a, 3个b, 1个c,所以不肯能,因为1个c不能被分组。
如果"abaabaabacc", 6个a, 3个b, 2个c,不可能被分组,因为,3个b和2个c没有公因
数。
如果"abaabaabaccc", 6个a, 3个b, 3个c,只能分3组,但明显不成立。O(n)。
对于单一字符,直接return false,
对于"abaabaabaaba",有8个a,4个b,能被分4或2组,分4组成立,2组也行。。
这个算法的麻烦在于如果最大公因数太大,比如有10000个a, 5000个b。最大公因数是
5000=5x5x5x5x2x2x2,有m个分组方式2, 5, 10, 20, 25, 50, 100, 125, 200, 500,
625
, 1000, 1250, 2500, 5000。判断要O(mn)个。所以还不是O(n)。
我觉得有的方式可以被排除,现在还没想清楚。
比如如果分5000组false被排除了,那么所有因子是2个分组是不是都不可能成立,分
1000组被排除了,是不是所用因子是5个分组是不是都不可能成立。
如果这个如上假设是对的,那么,这个算法,就有非常可能接近O(n)。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

u*****o
发帖数: 1224
67
讨论的热火朝天。。只有我一个人觉得lz是被黑了吗?店面考的这么难,存心的吗!
p****g
发帖数: 45
68
统计字母个数(字母数m>1),得个数最小值n, 把string分成n的公因数个(lglgn),复
杂度大概是O(nlglgn)。

【在 s**x 的大作中提到】
:
: 可以先统计所有字母的个数,取最小值。单一重复字母串就成了 is prime or not 了
: 。不过别的情况好像先统计帮助不大。

q****m
发帖数: 177
69
还是用kmp吧。 假设string是 s. 那么用kmp的话,pattern是s,要匹配的字符串是s.
substr(1),比pattern少第一个字符

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

m*********1
发帖数: 204
70
对的对的!
绝逼被黑了,我面试的还是一个intern,两个烙印。我专门开一贴说这个事情!

【在 u*****o 的大作中提到】
: 讨论的热火朝天。。只有我一个人觉得lz是被黑了吗?店面考的这么难,存心的吗!
相关主题
storm8 online test 讨论我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印
问一道n-ary tree 的题目问一个Pinterest的题目
求教电面遇到的一道pattern match的实现问个google老题的最佳解法
进入JobHunting版参与讨论
a*s
发帖数: 131
71
扫描一次
#include
#include
using namespace std;
const int min_len = 2;
bool is_multiple (string s) {
int r = s.length() - 1;
int t = s.length() - 1 - min_len;
int l = min_len;
while (t >= 0 && l <= s.length() / 2) {
while (s[t] != s[r]) {
--t;
++l;
}
for (int i = 0; i < l; ++i) {
if (s[t] != s[r]) {
r = s.length() - 1;
l = r - t;
break;
}
--t;
--r;
}
}
if (l == min_len && s[0] == s[1])
l = s.length();
return l <= s.length() / 2;
}
int main () {
string s[6] = {"abcabcabc", "bcdbcdbcde", "abcdabcd", "xyz", "aaaaaaaaaa
", "bcdbcdbcdebcdbcdbcde"};
for (int i = 0; i < 6; ++i)
cout << s[i] << " " << (is_multiple(s[i]) ? "True" : "False") <<
endl;
}
p******d
发帖数: 63
72
先用O(n)的Z algorithm算Z[i]=从i开始最长的prefix长度,i=1...n-1
例如
abcabcabc对应的Z={null, 0, 0, 3, 0, 0, 3, 0, 0}
aaabaaaaba对应的Z={null, 2, 1, 0, 3, 5, 2, 1, 0, 1}
aaaaaaaaaa对应的Z={null, 9, 8, 7, 6, 5, 4, 3, 2, 1}
之后扫一遍Z数组返回满足Z[i]==i的i值,到i-1的prefix就是答案
Z algorithm看这里http://codeforces.com/blog/entry/3107
c****p
发帖数: 6474
73
两个指针就搞定了吧……
poj里有这道题。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

c****p
发帖数: 6474
74
两个指针,head, tail,记循环节长度len为1
head初始都为0,tail为1。tail一直自增。
如果str[head] == str[tail], head自增。如果head>= len则归零
如果str[head] != str[tail],则len = tail。
扫完一遍查len和str.size()的关系就得了。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

m*********1
发帖数: 204
75
有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
2,输入一个String写代码返回T或者F
例子:
"abcabcabc" Ture 因为它把abc重复3次构成
"bcdbcdbcde" False 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" False 因为它不是某一个String重复
"aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
要求算法复杂度为O(n)
public boolean isMultiple(String s){
}
一紧张,大脑一片空白,直接不会做!!!
p*****2
发帖数: 21240
76
KMP吧。
f*****e
发帖数: 2992
77
确实,太牛了。

【在 p*****2 的大作中提到】
: KMP吧。
A*********c
发帖数: 430
78
build and check suffix tree.

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

z******h
发帖数: 22
79
直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
符串的开头必然是pattern的开头,并没有必要KMP。

★ 发自iPhone App: ChineseWeb 7.8
★ 发自iPhone App: ChineseWeb 7.8

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

w*******i
发帖数: 186
80
是的,先找第一个字符重复出现的地方,找到后假设这个字符与第一个字符间就是重复
的短字符串。然后继续扫描逐字匹配,不对就更新假设的重复的短字符串。
最后验证这个重复的短字符串长度是否够大。

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

相关主题
G onsite题求讨论F面经的一题
Interleave Strings那个题目有O(n)时间 O(1)空间算法么?没啥乐趣了
FB面试题一道 求解问一个KMP算法的问题
进入JobHunting版参与讨论
z***g
发帖数: 51
81
Good idea!但是怎么保证greedy就是最优呢?可能是我理解有问题,我怎么觉得9个a的
case greedy方法过不了。pattern=2 开始aaaaaaaaa这样一直找,知道最后才不行,也
就是第八个a,更新以后就是pattern=8了,这样找不出来。但是aaa,aaa,aaa pattern=
3是可分的。

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

l*****r
发帖数: 2122
82
反过来想,原string长度依次除以质数,从小到大。(2,3,5,7,11。。)
能整除的话,接着看是否匹配,不能的话看下一个稍大的质数。直到质数>n/2。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

l******t
发帖数: 37
83
In Python:
def isMultiple(string):
if not string:
return
step = 2
repeatstring = None
while step < len(string):
pat = string[:step]
if len(string) % len(pat) == 0:
if pat*(len(string)/len(pat)) == string:
if not repeatstring:
repeatstring = pat
step += 1
if repeatstring:
print 'repeatstring:', repeatstring
return len(set(repeatstring)) != 1
else:
return False
r*****e
发帖数: 30
84
public boolean isMultiple(String s){
if(s==null || s.length()<3) return false;
ArrayList pattern = new ArrayList();
pattern.add(s.charAt(0));
pattern.add(s.charAt(1));
int times = 1;
int pos = 0;
for(int i=2; i if(s.charAt(i)==pattern.get(pos)){
if(pos==pattern.size()-1){
times++;
pos = 0;
}
else{
pos++;
}
}
else{
for(int j=pattern.size(); j<=i; j++){
pattern.add(s.charAt(j));
}
times = 1;
pos = 0;
}
}
if(times==1 || pos!=0) return false;
boolean isSame = true;
for(int i=0; i if(pattern.get(i)!=pattern.get(0)){
isSame = false;
}
}
if(isSame) return false;
return true;
}
z******h
发帖数: 22
85
没问题,pattern="a" forever
事实上9个a这个case让我确定这个方法应该是标准答案...

pattern=
★ 发自iPhone App: ChineseWeb 7.8

【在 z***g 的大作中提到】
: Good idea!但是怎么保证greedy就是最优呢?可能是我理解有问题,我怎么觉得9个a的
: case greedy方法过不了。pattern=2 开始aaaaaaaaa这样一直找,知道最后才不行,也
: 就是第八个a,更新以后就是pattern=8了,这样找不出来。但是aaa,aaa,aaa pattern=
: 3是可分的。
:
: pattern

m*****n
发帖数: 2152
86
"bcdbcdbcdebcdbcdbcde" 是true 还是false啊?

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

m*****n
发帖数: 2152
87
为什么啊,“bcdbcdbcdebcdbcdbcde”可以分成"bcdbcdbcde" x 2啊。而且10个a尽然
也是false,说"aa" x 5和 "aaaaa" x2都不算,不能理解啊。

【在 f*****e 的大作中提到】
: 确实,太牛了。
f*****e
发帖数: 2992
88
没看清楚,应该是true。

【在 m*****n 的大作中提到】
: 为什么啊,“bcdbcdbcdebcdbcdbcde”可以分成"bcdbcdbcde" x 2啊。而且10个a尽然
: 也是false,说"aa" x 5和 "aaaaa" x2都不算,不能理解啊。

A*********c
发帖数: 430
89
great idea!

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

l*****4
发帖数: 267
90
贡献一下我的,试过大家提到的所有case, 都可以
利用string本身作为pattern
如果前半部分都match的话,指针要过中点
只判断是否过中点的话,“aaaaabaaaa”这种就判断错误
是因为后一段短,从指针到pattern结束的位置没有被扫到
如果把指针到string 末尾的再和string前一部分相同长度的段对比,如果是重复,那
就真的是true
如果没办法重复,就说明漏扫了不同的部分,false
解释的可能不清楚,还是看代码吧,java
public boolean isMultiple(String s) {
if (s == null || s.length() == 0) {
return false;
}
int len = s.length();
if (len == 1) {
return true;
}
if (len == 2) {
return s.charAt(0) == s.charAt(1);
}
int left = 0;
for (int i = 1; i < len; i++) {
char c = s.charAt(i);
if (c == s.charAt(left)) {
left++;
} else {
left = 0;
}
}
if (len % 2 == 0 && left >= (s.length() / 2 - 1)) {
String leftHalf = s.substring(0, s.length() - left);
String rightHalf = s.substring(left);
if (leftHalf.equals(rightHalf))
return true;
} else if (len % 2 != 0 && left > (s.length() / 2)){
String leftHalf = s.substring(0, s.length() - left);
String rightHalf = s.substring(left);
if (leftHalf.equals(rightHalf))
return true;
}
return false;
}
附上试过的text cases,请大家指正
"abcabcabcab" // false
"bcdbcdbcde" //false
"abcdabcd" //true
"xyzxy" //false
"aaaaaaaaaaaaaaaaaaaaa" //true
"bcdbcdbcdbcdbcdbc" //fasle
"aaaaabaaaa" //false
相关主题
微软电面Longest common string问题
问2道面试题问几道较难的字符串题
查找substr的问题finds all repeated substrings in the string --- YAHOO interview question
进入JobHunting版参与讨论
x****g
发帖数: 1512
91
不理解。
ababcababc.
abaaba.
怎么都能成功呢?

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

j*****8
发帖数: 3635
92
那位兄台的算法针对abaaba过不去,做个小改动;如果发现不匹配当前pattern,就和
首字母比较一下;如果和首字母一样,pattern改成首字母到当前字母的前一位;否则
pattern改成首字母到当前字母

【在 x****g 的大作中提到】
: 不理解。
: ababcababc.
: abaaba.
: 怎么都能成功呢?
:
: pattern

z******h
发帖数: 22
93
恩我那个是有问题
你这个对于abaaaaaaba这样的怎么处理?好像还是要出问题。

【在 j*****8 的大作中提到】
: 那位兄台的算法针对abaaba过不去,做个小改动;如果发现不匹配当前pattern,就和
: 首字母比较一下;如果和首字母一样,pattern改成首字母到当前字母的前一位;否则
: pattern改成首字母到当前字母

j*****8
发帖数: 3635
94
没问题阿,这个返回false
整个字符串走完后,check pattern的长度,如果等于n,返回false

【在 z******h 的大作中提到】
: 恩我那个是有问题
: 你这个对于abaaaaaaba这样的怎么处理?好像还是要出问题。

x****g
发帖数: 1512
95
我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
溯。
不证明这一点,这种修正都会引起反例。
比方说。
aaaba aaaba
你修改后也不行。
a引起失败在b,
所以变成aaab.
这次引起失败在aaabaaa[a]
你取不回aaaba了,呵呵。

【在 j*****8 的大作中提到】
: 那位兄台的算法针对abaaba过不去,做个小改动;如果发现不匹配当前pattern,就和
: 首字母比较一下;如果和首字母一样,pattern改成首字母到当前字母的前一位;否则
: pattern改成首字母到当前字母

z******h
发帖数: 22
96
的确是,看来这条路有问题。
刚才找了半天反例没找到,被你发现了...

【在 x****g 的大作中提到】
: 我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
: 溯。
: 不证明这一点,这种修正都会引起反例。
: 比方说。
: aaaba aaaba
: 你修改后也不行。
: a引起失败在b,
: 所以变成aaab.
: 这次引起失败在aaabaaa[a]
: 你取不回aaaba了,呵呵。

b****f
发帖数: 138
97
Passed Test Run, Not sure if having other bugs
class Solution {
public:
bool isMultiple (string s){
int N=s.size();
if(N<3) return false;
int len=1;
int start=0;
for(int i=1;i if(s[start]==s[i]){
start++;
if(start>=len) start=0;
}
else{
len=i+1;
start=0;
}
if(len>N/2) return false;
}
return len!=1;
}
};
void main() {
Solution sol;
cout< cout< cout< cout< cout< _getch();
}
x****g
发帖数: 1512
98
你这个长度增加1,但i不回溯?
感觉你pass不过我的case ? 呵呵。
aaaba aaaba
先讲原理后写代码比较好。

【在 b****f 的大作中提到】
: Passed Test Run, Not sure if having other bugs
: class Solution {
: public:
: bool isMultiple (string s){
: int N=s.size();
: if(N<3) return false;
: int len=1;
: int start=0;
: for(int i=1;i: if(s[start]==s[i]){

z******h
发帖数: 22
99

~~~~~~~~~~~~~~~~~~~~Re

【在 x****g 的大作中提到】
: 你这个长度增加1,但i不回溯?
: 感觉你pass不过我的case ? 呵呵。
: aaaba aaaba
: 先讲原理后写代码比较好。

j*****8
发帖数: 3635
100
有道理。。

【在 x****g 的大作中提到】
: 我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
: 溯。
: 不证明这一点,这种修正都会引起反例。
: 比方说。
: aaaba aaaba
: 你修改后也不行。
: a引起失败在b,
: 所以变成aaab.
: 这次引起失败在aaabaaa[a]
: 你取不回aaaba了,呵呵。

相关主题
还真从来没见过考KMP之类string matching算法的求教电面遇到的一道pattern match的实现
storm8 online test 讨论我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印
问一道n-ary tree 的题目问一个Pinterest的题目
进入JobHunting版参与讨论
b****f
发帖数: 138
101
前面的评论没看,i不回溯的确过不了,这个暴力法都可以过,但貌似超时了,感觉现
在只能用KMP了
class Solution {
public:
bool isMultiple (string s){
int N=s.size();
if(N<3) return false;
int len=1;
int start=0;
for(int i=1;i if(s[start]==s[i]){
start++;
if(start>=len) start=0;
}
else{
len++;
i=len-1;
start=0;
}
if(len>N/2) return false;
}
return len!=1;
}
};
void main() {
Solution sol;
cout< cout< cout< cout< cout< cout< cout< _getch();
}
s******t
发帖数: 229
102
abaabaaba
怎么扫?

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

k****s
发帖数: 16
103
这个思路非常好。
问题应该只出现在真实pattern的prefix和suffix相同。
1. prefix和suffix相同且不为同一字母,之前方法(直接看到从前)可解。
2. prefix和suffix相同且为同一字母,这就必须得Pattern+1了。
所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题,
那么Pattern+1, 否则就 直接看到从前。
比如 aba aba 失败在第三个a 应该match的是b,所以pattern+1
aaaba aaaba最后失败在aaabaaa[a],应该match的是b,所以pattern+1.
更新完pattern后,只需要把当前match的b前移一位match,来保证O(n)

【在 x****g 的大作中提到】
: 我觉得核心问题是什么使得你能够不在原来的Pattern+1而是直接看到当前从而避免回
: 溯。
: 不证明这一点,这种修正都会引起反例。
: 比方说。
: aaaba aaaba
: 你修改后也不行。
: a引起失败在b,
: 所以变成aaab.
: 这次引起失败在aaabaaa[a]
: 你取不回aaaba了,呵呵。

s******d
发帖数: 424
104
你这得扫多少次?O(N)不可能啊

【在 l******t 的大作中提到】
: In Python:
: def isMultiple(string):
: if not string:
: return
: step = 2
: repeatstring = None
: while step < len(string):
: pat = string[:step]
: if len(string) % len(pat) == 0:
: if pat*(len(string)/len(pat)) == string:

s******t
发帖数: 229
105

目前还没想到什么反例。。。想到反例估计又要fix bug

【在 k****s 的大作中提到】
: 这个思路非常好。
: 问题应该只出现在真实pattern的prefix和suffix相同。
: 1. prefix和suffix相同且不为同一字母,之前方法(直接看到从前)可解。
: 2. prefix和suffix相同且为同一字母,这就必须得Pattern+1了。
: 所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题,
: 那么Pattern+1, 否则就 直接看到从前。
: 比如 aba aba 失败在第三个a 应该match的是b,所以pattern+1
: aaaba aaaba最后失败在aaabaaa[a],应该match的是b,所以pattern+1.
: 更新完pattern后,只需要把当前match的b前移一位match,来保证O(n)

H*********a
发帖数: 34
106
我也发一个想法,从string的第2位开始扫(为了保证那个子string的长度为2),当前
位的char和string首char一样的时候,就以首位到当前位的子string为模型,匹配后面
的相隔同等位置,同等长度的子string。这个方法不能处理"aaaaaaaaaa",因为认为这
是"aaaaa"乘以2。
bool check(int l, int n, string s) {
if (n % l != 0)
return false;
for (int j = 1; j < n/l; j++) {
if (s.substr(0, l) != s.substr(j*l, l))
return false;
}
return true;
}
bool isMultiple(string s) {
int n = s.size();
if (n <= 3)
return false;
for (int i = 2; i <= n/2; i++) {
if (s[i] == s[0]) {
if (check(i, n, s))
return true;
}
}
return false;
}

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

s******d
发帖数: 424
107
一紧张确实容易的题也想不起来
看看这个版本有错误吗
bool isMultiple (string s){
int N = s.size();
if(N < 4) return false;
int start = 0;
int pattern_end = 0;
for(int i=1;i {
if(s[start] == s[i])
{
if(start == 0)
pattern_end = i - 1;
start++;
}
else
{
pattern_end = 0;
start=0;
if(s[0] == s[i])
{
start = 1;
pattern_end = i-1;
}
}
if(pattern_end >= N/2)
return false;
}
return pattern_end > 0 && (N % (pattern_end+1) == 0);
}
错的,还是需要回溯
s******d
发帖数: 424
108
beewmf的最后一个也有bug,考虑 abcabcabcab
下面是修改过的
bool isMultiple (string s){
int N=s.size();
if(N<4) return false;
int len=1;
int start=0;
for(int i=1;i if(s[start]==s[i]){
start++;
if(start>=len) start=0;
}
else{
len++;
i=len-1; // start from len
start=0;
}
if(len>N/2) return false;
}
return len!=1 && (N % len == 0);
}
M*******a
发帖数: 1633
109
这显然suffix tree么
x****g
发帖数: 1512
110
抱歉,没看懂。
1:为什么“应该”只出现在?
2:每次pattern变化都要判prefix & suffix? 这个不改变O(n)?
3: 为啥更新pattern+1之后,只需把当前前移一位,而不需要回溯?
另外有人提的KMP具体怎么做?我其实也挺质疑,哈哈。

【在 k****s 的大作中提到】
: 这个思路非常好。
: 问题应该只出现在真实pattern的prefix和suffix相同。
: 1. prefix和suffix相同且不为同一字母,之前方法(直接看到从前)可解。
: 2. prefix和suffix相同且为同一字母,这就必须得Pattern+1了。
: 所以只需要找到pattern第一个和首字母不同的字母。每次比较如果是match它出问题,
: 那么Pattern+1, 否则就 直接看到从前。
: 比如 aba aba 失败在第三个a 应该match的是b,所以pattern+1
: aaaba aaaba最后失败在aaabaaa[a],应该match的是b,所以pattern+1.
: 更新完pattern后,只需要把当前match的b前移一位match,来保证O(n)

相关主题
问一个Pinterest的题目Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
问个google老题的最佳解法FB面试题一道 求解
G onsite题求讨论F面经的一题
进入JobHunting版参与讨论
s******d
发帖数: 424
111
suffix tree太复杂了,面试的时候能写出来吗
z*********e
发帖数: 10149
112
没看懂,为什么10个a是false?
为什么不能看成5个a重复2次或者2个a重复5次?
x****g
发帖数: 1512
113
假设s=S0...Sn-1
我觉得我会选择判定SkSk+1=[Sn-1][S0]位置出的k,
如果k+1能整除整体长度,那么S0...Sk就是当前的pattern,
比较成功的话就一直向前,
如果失败在某一处的话,那么pattern更新为到失败处之后的那个满足条件的k'.
需要思考细节,呵呵。
k****s
发帖数: 16
114

我描述有问题,不过那个方法确实也有问题,过不了 abaab abaab 。
我来再给个吧。
列出所有公因数,O(logn)。
pattern长度只能在公因数里,每次不match,增加pattern长度到公因数里的下一个。
再用kmp里的性质,来减少回溯。

【在 x****g 的大作中提到】
: 抱歉,没看懂。
: 1:为什么“应该”只出现在?
: 2:每次pattern变化都要判prefix & suffix? 这个不改变O(n)?
: 3: 为啥更新pattern+1之后,只需把当前前移一位,而不需要回溯?
: 另外有人提的KMP具体怎么做?我其实也挺质疑,哈哈。

k****s
发帖数: 16
115

哦, 才看到,我说的是跟你这个一样吧。

【在 x****g 的大作中提到】
: 假设s=S0...Sn-1
: 我觉得我会选择判定SkSk+1=[Sn-1][S0]位置出的k,
: 如果k+1能整除整体长度,那么S0...Sk就是当前的pattern,
: 比较成功的话就一直向前,
: 如果失败在某一处的话,那么pattern更新为到失败处之后的那个满足条件的k'.
: 需要思考细节,呵呵。

z******h
发帖数: 22
116
这个前面有人说过了,而且应该不需要KMP因为不用回朔

★ 发自iPhone App: ChineseWeb 7.8

【在 k****s 的大作中提到】
:
: 哦, 才看到,我说的是跟你这个一样吧。

k****s
发帖数: 16
117

回溯还是要的吧。
比如
字符串 abaab abaab
当pattern 为aba
abaab abaab
第3个b不match
pattern 增到 abaab,要回溯到pattern+1位置开始匹配

【在 z******h 的大作中提到】
: 这个前面有人说过了,而且应该不需要KMP因为不用回朔
:
: ★ 发自iPhone App: ChineseWeb 7.8

a*******e
发帖数: 47
118
aaabbca aaabbca 何解?

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

w********s
发帖数: 1570
119
brute force多简单,复杂度 bool isPrefix(char* pattern, char* str, int size)
{
for (int i = 0; i < size && str[i] != '\0'; ++i)
{
if (str[i] != pattern[i])
return false;
}
return true;
}
int repeat(char* str)
{
int length = strlen(str);
int count = 0;
for (int i = 2; i <= length / 2; ++i)
{
if (length % i > 0)
continue;
count = 0;
int p = length / i;
for (int j = 1; j < p; ++j)
{
if (isPrefix(str, str + i * j, i))
count++;
else
{
count = 0;
break;
}
}
if (count > 0) return count + 1;
}
return 0;
}
M*******a
发帖数: 1633
120
人说了要O(n)

【在 w********s 的大作中提到】
: brute force多简单,复杂度: bool isPrefix(char* pattern, char* str, int size)
: {
: for (int i = 0; i < size && str[i] != '\0'; ++i)
: {
: if (str[i] != pattern[i])
: return false;
: }
: return true;
: }

相关主题
没啥乐趣了问2道面试题
问一个KMP算法的问题查找substr的问题
微软电面Longest common string问题
进入JobHunting版参与讨论
x****g
发帖数: 1512
121
不行啊,坑爹的,呵呵.
长度分解也很重要?
举个例子来说,一个无比大的素数含了全相同的单个字符,要是纯字符串比,怎么也到不
了O(N).
有长度判定的话直接就false. 呵呵
x****g
发帖数: 1512
122
我想的不对啊,呵呵.
adb acb adb adb acb adb

【在 k****s 的大作中提到】
:
: 回溯还是要的吧。
: 比如
: 字符串 abaab abaab
: 当pattern 为aba
: abaab abaab
: 第3个b不match
: pattern 增到 abaab,要回溯到pattern+1位置开始匹配

s**x
发帖数: 7506
123

可以先统计所有字母的个数,取最小值。单一重复字母串就成了 is prime or not 了
。不过别的情况好像先统计帮助不大。

【在 x****g 的大作中提到】
: 不行啊,坑爹的,呵呵.
: 长度分解也很重要?
: 举个例子来说,一个无比大的素数含了全相同的单个字符,要是纯字符串比,怎么也到不
: 了O(N).
: 有长度判定的话直接就false. 呵呵

m********l
发帖数: 791
124
按照楼主给的test case
单一字符的话就直接return false了啊

【在 s**x 的大作中提到】
:
: 可以先统计所有字母的个数,取最小值。单一重复字母串就成了 is prime or not 了
: 。不过别的情况好像先统计帮助不大。

m********l
发帖数: 791
125
找所有factors应该是O(sqrt(n))吧?

【在 k****s 的大作中提到】
:
: 回溯还是要的吧。
: 比如
: 字符串 abaab abaab
: 当pattern 为aba
: abaab abaab
: 第3个b不match
: pattern 增到 abaab,要回溯到pattern+1位置开始匹配

j**h
发帖数: 1230
126
写个笨的。
length = M * N * ... * Z: M, N, ..., Z are prime numbers.
从M到Z挨个试:
split input string into M parts, these M parts must be same.
w****y
发帖数: 56
127
is it the problem here?
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
A typical problem seen quite often is: given a string find its shortest
substring, such that the concatenation of one or more copies of it results
in the original string. Again the problem can be reduced to the properties
of the failure function. Let's consider the string
A B A B A B
and all its proper suffix/prefixes in descending order:
1 A B A B
2 A B
3 /the empty string/
Every such suffix/prefix uniquely defines a string, which after being "
inserted" in front of the given suffix/prefix gives the initial string. In
our case:
1 A B
2 A B A B
3 A B A B A B
Every such "augmenting" string is a potential "candidate" for a string, the
concatenation of several copies of which results in the initial string. This
follows from the fact that it is not only a prefix of the initial string
but also a prefix of the suffix/prefix it "augments". But that means that
now the suffix/prefix contains at least two copies of the "augmenting"
string as a prefix (since it's also a prefix of the initial string) and so
on. Of course if the suffix/prefix under question is long enough. In other
words, the length of a successful "candidate" must divide with no remainder
the length of the initial string.
So all we have to do in order to solve the given problem is to iterate
through all proper suffixes/prefixes of the initial string in descending
order. This is just what the "failure function" is designed for. We iterate
until we find an "augmenting" string of the desired length (its length
divides with no remainder the length of the initial string) or get to the
empty string, in which case the "augmenting" string that meets the above
requirement will be the initial string itself.
w********s
发帖数: 1570
128
建立每个字母的出现位置表,举个例子aaabbcaaaabbca
a:0,1,2,6,7,8,9,13
b:3,4,10,11
c:5,12
然后建立每个字母的可能
a:1,2,6,7
b:1,7
c:7
然后取重复出现的最小值:7
重复次数就是length/7
O(n)可以解决吧。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

w********s
发帖数: 1570
129
#include "stdafx.h"
#include
#include
#include
#include
typedef std::map> MyMap;
MyMap m;
int repeat2(char* str)
{
for (int i = 0; i < strlen(str); ++i)
{
char c = str[i];
if (m.find(c) == m.end())
{
std::vector v;
v.push_back(i);
m[c] = v;
}
else
{
m[c].push_back(i);
}
}
int* count = new int[strlen(str)];
memset(count, 0, strlen(str) * sizeof(int));
int nChars = 0;
for (MyMap::iterator it = m.begin(); it != m.end(); ++it)
{
char c = it->first;
std::vector v = it->second;
if (v.size() < 2) return 0;
for (int i = 1; i <= v.size() / 2; ++i)
{
int d = v[i] - v[0];
count[d]++;
}
nChars++;
}
for (int i = 0; i < strlen(str); ++i)
{
if (count[i] == nChars)
{
if (strlen(str) % i > 0 || i == 1)
return 0;
else
return strlen(str) / i;
}
}
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
char abc[] = "aaabbcaaaabbca";
std::cout << repeat2(abc);
getchar();
}
w********s
发帖数: 1570
130
以上所有测试都通过了,并且复杂度O(n)
相关主题
问几道较难的字符串题storm8 online test 讨论
finds all repeated substrings in the string --- YAHOO interview question问一道n-ary tree 的题目
还真从来没见过考KMP之类string matching算法的求教电面遇到的一道pattern match的实现
进入JobHunting版参与讨论
m*********1
发帖数: 204
131
昨天晚上睡不着,上来发的,没想到一天有那么多回复了。看了大家的回复,我觉得我
这个题目不简单啊。呵呵。。。
不过这个题目我后来仔细思考过,我的做法是这样的:
1.两头同时开始扫,找到base case: 当substring(0,i) == substring(j,n)的时候,
我假设substring(0,i)为这个重复的base case. 这里n是原String的length
这里可以优化的是,如前面同学所说,i不能被length整除的话,就不用比较,直接跳
过去
2.从1找到base case以后,两头切掉,留下中间部分substring(i,j),先看一下长度,
能不能整除i,不能就直接false,可以的话,写个循环,每次切i长度下来,和base
case对比一下是不是相等,直到结束。
因为很多不能整除的数可以跳过去,这个做法的worse case 是长度正好是2^n的String
,并且base case正好是2^k的长度的情况。
比如 ababababababacab 这样找到base case = ab,然后要切到最后才发现ac,但是
感觉还是能满足O(n)
我贴下我的代码,如有错误请指正。另外,不知道KMP怎么写,知道的同学请指教。
public static boolean Repeat(String s){
int len = s.length();
if(len < 4)
return false;
for(int i=1;i<=len/2;i++){
if((len % i) == 0){
if(s.substring(0,i).equals(s.substring(len-i,len))){
String base = s.substring(0,i);
//Exclude all "a"s
int x = base.length()-1;
while(x > 0 && s.charAt(x) == s.charAt(x-1)){
x--;
}
if(x > 0){

if(len/2 == i){
return true;
}
else{
String tmp = s.substring(i,len-i);
if(tmp.length() % i != 0)
return false;
int k = tmp.length();
int t = tmp.length() - i;
while(t >= 0 && tmp.substring(t,k).equals(base) ){
t = t - i;
k = k - i;
}
if(k == 0)
return true;

}
}
}


}


}
return false;
}
m*********1
发帖数: 204
132
上面我说错了一个地方。
如果找出来的base case,后面切中间部分的时候发现不匹配,还要继续找下一个base
case,直到i = length/2 为止。 (我前面说return false,是不对的)
w********s
发帖数: 1570
133
你的优化不解决根本问题,我的算法比你简单多了

【在 m*********1 的大作中提到】
: 昨天晚上睡不着,上来发的,没想到一天有那么多回复了。看了大家的回复,我觉得我
: 这个题目不简单啊。呵呵。。。
: 不过这个题目我后来仔细思考过,我的做法是这样的:
: 1.两头同时开始扫,找到base case: 当substring(0,i) == substring(j,n)的时候,
: 我假设substring(0,i)为这个重复的base case. 这里n是原String的length
: 这里可以优化的是,如前面同学所说,i不能被length整除的话,就不用比较,直接跳
: 过去
: 2.从1找到base case以后,两头切掉,留下中间部分substring(i,j),先看一下长度,
: 能不能整除i,不能就直接false,可以的话,写个循环,每次切i长度下来,和base
: case对比一下是不是相等,直到结束。

m*********1
发帖数: 204
134
我没看明白你的算法
能不能再解释一下
取出位置以后的后面一步,位置的可能?

【在 w********s 的大作中提到】
: 你的优化不解决根本问题,我的算法比你简单多了
w********s
发帖数: 1570
135
建立每个字母的出现位置表,举个例子aaabbcaaaabbca
a:0,1,2,6,7,8,9,13
b:3,4,10,11
c:5,12
然后建立每个字母的可能
a:1,2,6,7 (就是1-0, 2-0, 6-0, 7-0)
b:1,7
c:7
map[1] = 2次
map[2] = 1次
map[6] = 1次
map[7] = 3次
所以长度为7。元字符串长14, 14/7=2遍。

【在 m*********1 的大作中提到】
: 我没看明白你的算法
: 能不能再解释一下
: 取出位置以后的后面一步,位置的可能?

w********s
发帖数: 1570
136
想了一下,这个也有问题。
至今没有O(n)解。

【在 w********s 的大作中提到】
: 建立每个字母的出现位置表,举个例子aaabbcaaaabbca
: a:0,1,2,6,7,8,9,13
: b:3,4,10,11
: c:5,12
: 然后建立每个字母的可能
: a:1,2,6,7 (就是1-0, 2-0, 6-0, 7-0)
: b:1,7
: c:7
: map[1] = 2次
: map[2] = 1次

w********s
发帖数: 1570
137
素数的话,n以内有n/(ln(n)-1.08)个数,所以还是满足不了O(n)

【在 j**h 的大作中提到】
: 写个笨的。
: length = M * N * ... * Z: M, N, ..., Z are prime numbers.
: 从M到Z挨个试:
: split input string into M parts, these M parts must be same.

b**y
发帖数: 22
138
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::string;
int main(int argc, char* argv[])
{
cout<<"Please input a string"< string InputStr;
cin>>InputStr;
string subStr;
int i = InputStr.length()-1;
while(i>0)
{
subStr=InputStr.substr(i);
for(int j=i-1;j>=0;j--)
{
if(InputStr[j]!=subStr[(j%subStr.length())])
{
i=j;
break;
}
if(j==0)
{
//Done should be a true if size is bigger than 2 and less than half
if((subStr.size()>=2)&&(subStr.size() {
cout<<"Yes true"< return 0;
}
else
{
cout<<"No false"< return 0;
}

}
}
}
cout<<"No false"< return 0;
}
r*****t
发帖数: 68
139
my idea is to reassemble a string by moving certain number of chars from the
end to the head, and compare the new string with the old. if match, it
means the moved portion is the repeative portion. Can ignore the complexity
of string comparison?
int n=mInput.size()
if(n<=2)
return false;
string newstr(n, mInput[0]);//consist of unique char
if(mInput.compare(newstr)==0)
return false;
for i>=2 && i<=n/2)
{
if( (n-i)%i==0 )
{
//move last ith chars to the front
newstr=mInput.substr(n-i)+mInput.substr(0,n-i);
if(mInput.compare(newstr)==0)
return true;
}
return false;

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

m*****n
发帖数: 2152
140
有一个思路,
首先把字符串统计字符个数 O(1),比如,
“abaabaabac”
就是6个a, 3个b, 1个c,所以不肯能,因为1个c不能被分组。
如果"abaabaabacc", 6个a, 3个b, 2个c,不可能被分组,因为,3个b和2个c没有公因
数。
如果"abaabaabaccc", 6个a, 3个b, 3个c,只能分3组,但明显不成立。O(n)。
对于单一字符,直接return false,
对于"abaabaabaaba",有8个a,4个b,能被分4或2组,分4组成立,2组也行。。
这个算法的麻烦在于如果最大公因数太大,比如有10000个a, 5000个b。最大公因数是
5000=5x5x5x5x2x2x2,有m个分组方式2, 5, 10, 20, 25, 50, 100, 125, 200, 500,
625
, 1000, 1250, 2500, 5000。判断要O(mn)个。所以还不是O(n)。
我觉得有的方式可以被排除,现在还没想清楚。
比如如果分5000组false被排除了,那么所有因子是2个分组是不是都不可能成立,分
1000组被排除了,是不是所用因子是5个分组是不是都不可能成立。
如果这个如上假设是对的,那么,这个算法,就有非常可能接近O(n)。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

相关主题
求教电面遇到的一道pattern match的实现问个google老题的最佳解法
我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印G onsite题求讨论
问一个Pinterest的题目Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
进入JobHunting版参与讨论
u*****o
发帖数: 1224
141
讨论的热火朝天。。只有我一个人觉得lz是被黑了吗?店面考的这么难,存心的吗!
p****g
发帖数: 45
142
统计字母个数(字母数m>1),得个数最小值n, 把string分成n的公因数个(lglgn),复
杂度大概是O(nlglgn)。

【在 s**x 的大作中提到】
:
: 可以先统计所有字母的个数,取最小值。单一重复字母串就成了 is prime or not 了
: 。不过别的情况好像先统计帮助不大。

q****m
发帖数: 177
143
还是用kmp吧。 假设string是 s. 那么用kmp的话,pattern是s,要匹配的字符串是s.
substr(1),比pattern少第一个字符

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

m*********1
发帖数: 204
144
对的对的!
绝逼被黑了,我面试的还是一个intern,两个烙印。我专门开一贴说这个事情!

【在 u*****o 的大作中提到】
: 讨论的热火朝天。。只有我一个人觉得lz是被黑了吗?店面考的这么难,存心的吗!
a*s
发帖数: 131
145
扫描一次
#include
#include
using namespace std;
const int min_len = 2;
bool is_multiple (string s) {
int r = s.length() - 1;
int t = s.length() - 1 - min_len;
int l = min_len;
while (t >= 0 && l <= s.length() / 2) {
while (s[t] != s[r]) {
--t;
++l;
}
for (int i = 0; i < l; ++i) {
if (s[t] != s[r]) {
r = s.length() - 1;
l = r - t;
break;
}
--t;
--r;
}
}
if (l == min_len && s[0] == s[1])
l = s.length();
return l <= s.length() / 2;
}
int main () {
string s[6] = {"abcabcabc", "bcdbcdbcde", "abcdabcd", "xyz", "aaaaaaaaaa
", "bcdbcdbcdebcdbcdbcde"};
for (int i = 0; i < 6; ++i)
cout << s[i] << " " << (is_multiple(s[i]) ? "True" : "False") <<
endl;
}
p******d
发帖数: 63
146
先用O(n)的Z algorithm算Z[i]=从i开始最长的prefix长度,i=1...n-1
例如
abcabcabc对应的Z={null, 0, 0, 3, 0, 0, 3, 0, 0}
aaabaaaaba对应的Z={null, 2, 1, 0, 3, 5, 2, 1, 0, 1}
aaaaaaaaaa对应的Z={null, 9, 8, 7, 6, 5, 4, 3, 2, 1}
之后扫一遍Z数组返回满足Z[i]==i的i值,到i-1的prefix就是答案
Z algorithm看这里http://codeforces.com/blog/entry/3107
c****p
发帖数: 6474
147
两个指针就搞定了吧……
poj里有这道题。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

c****p
发帖数: 6474
148
两个指针,head, tail,记循环节长度len为1
head初始都为0,tail为1。tail一直自增。
如果str[head] == str[tail], head自增。如果head>= len则归零
如果str[head] != str[tail],则len = tail。
扫完一遍查len和str.size()的关系就得了。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

u*****o
发帖数: 1224
149
这个答案很不错,想问问
如果head>= len则归零
这个条件什么时候为true呢? head会比len大吗?

【在 c****p 的大作中提到】
: 两个指针,head, tail,记循环节长度len为1
: head初始都为0,tail为1。tail一直自增。
: 如果str[head] == str[tail], head自增。如果head>= len则归零
: 如果str[head] != str[tail],则len = tail。
: 扫完一遍查len和str.size()的关系就得了。

l*****i
发帖数: 13
150
abaaabaa False
想不出来只扫一遍的做法啊

【在 a*s 的大作中提到】
: 扫描一次
: #include
: #include
: using namespace std;
: const int min_len = 2;
: bool is_multiple (string s) {
: int r = s.length() - 1;
: int t = s.length() - 1 - min_len;
: int l = min_len;
: while (t >= 0 && l <= s.length() / 2) {

相关主题
FB面试题一道 求解问一个KMP算法的问题
F面经的一题微软电面
没啥乐趣了问2道面试题
进入JobHunting版参与讨论
c****p
发帖数: 6474
151
会啊。
ababababababab这种情况Len=2

【在 u*****o 的大作中提到】
: 这个答案很不错,想问问
: 如果head>= len则归零
: 这个条件什么时候为true呢? head会比len大吗?

t*****a
发帖数: 106
152
你这个就是27楼beewmf的算法,最多是amortized的O(n),还是要回溯的。

【在 c****p 的大作中提到】
: 两个指针,head, tail,记循环节长度len为1
: head初始都为0,tail为1。tail一直自增。
: 如果str[head] == str[tail], head自增。如果head>= len则归零
: 如果str[head] != str[tail],则len = tail。
: 扫完一遍查len和str.size()的关系就得了。

A****L
发帖数: 138
153
贴一个 O(n) 解法, java code 用了KMP 里的prefix function. 思路是前面有人提到
的 topcoder连接里讲解的。
public boolean checkRepetition(String s) {
int m = s.length();
if(m<4) return false;
for(int i=1;i if(s.charAt(i)!=s.charAt(i-1)) break;
if(i==m-1) return false;
}
int[] pattern = prefixFunction(s);
int p = pattern[m];
while(p>1) {
if(p%(m-p)==0) return true;
p=pattern[p];
}
return false;
}

public int[] prefixFunction(String p) {
int m = p.length();
int [] next = new int[m+1];
next[0]=next[1]=0;
int k=0;
for(int q = 2;q<=m;q++) {
while(k>0 && p.charAt(q-1)!=p.charAt(k))
k=next[k];
if(p.charAt(k)==p.charAt(q-1))
k=k+1;
next[q] = k;
}
return next;
}


【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

x*****0
发帖数: 452
154
mark
m*****i
发帖数: 10
155
public boolean isMultiple(String s) {
if(s==null || s.length()==0)
return true;
int maxInterval = 1;
HashMap map = new HashMap();
char[] chs = s.toCharArray();
for(int i=0; i if(!map.containsKey(chs[i]))
map.put(chs[i], i);
else{
int pre = map.get(chs[i]);
if(maxInterval<(i-pre)){
maxInterval = i-pre;
}
map.put(chs[i], i);
}
}
int length = chs.length;
if(maxInterval==1){
if(length%2==0 && length/2>1)
return true;
for(int i=3; i*i<=length; i+=2){
if(length%i==0 && length/i>1)
return true;
}
return false;
}
if(length%maxInterval!=0)
return false;
List list = new ArrayList();
for(int i=0; i list.add(s.substring(i, i+maxInterval));
if(list.size()==1)
return false;
String pre = list.get(0);
for(String str : list){
if(!pre.equals(str))
return false;
}
return true;
}
Test case:
"abcabcabcab" // false
"bcdbcdbcde" //false
"abcdabcd" //true
"xyzxy" //false
"aaaaaaaaaaaaaaaaaaaaa" //true
"bcdbcdbcdbcdbcdbc" //fasle
"aaaaabaaaa" //false
bcdbcdbcdebcdbcdbcde //true

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

c*******2
发帖数: 60
156
Given String S of length n. Return false if n < 4.
Let T = S.substring(1) + S.substring(0,n-1), return true if S is substring
of T
If "aaaaaaaaaa" is False, then return T.indexOf(S) > 0

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

r****7
发帖数: 2282
157
challenge me
bool isRepeat(string s) {
bool ret = false;
int sz = s.size();
vector pi(sz, 0);
int k = 0;
for (int i = 1; i < sz; i ++) {
while (k != 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k ++;
}
pi[i] = k;
}
int d = sz - pi[sz - 1];

int idx = d - 1;
int expectedRes = 0;

bool rFlag = false;
if (d < 2) {
ret = false;
goto e;
}
while (true) {
if (idx == sz - 1) {
ret = rFlag;
goto e;
}
if (idx >= sz) {
ret = false;
goto e;
}
if (pi[idx] != expectedRes) {
ret = false;
goto e;
} else {
idx += d;
expectedRes += d;
}
rFlag = true;
}
e:
printf("string %s ret is %d.\n", s.c_str(), ret);
return ret;
}
int main() {
bool ret = isRepeat("abcabcabc");
ret = isRepeat("bcdbcdbcde");
ret = isRepeat("abcdabcd");
ret = isRepeat("xyz");
ret = isRepeat("aaaaaaaaaa");
ret = isRepeat("aaaba");
ret = isRepeat("aaaba aaaba");
ret = isRepeat("ababeabab");
return 0;
}

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

p**p
发帖数: 742
158
这题用KMP吧。检查preprocess部分生产的array l 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件:
1. l[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-l[n-1])就是repeating pattern;
3. l[n-1]/(length of the repeating pattern) >= 1;
4. l[n-1] % (length of the repeating pattern) == 0.
比如:
"abcabcabc" -> [0, 0, 0, 1, 2, 3, 4, 5, 6]
"abcdabcd"-> [0, 0, 0, 0, 1, 2, 3, 4]
几个false cases:
"bcdbcdbcdebcdbcdbcd" -> [0, 0, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7,
8, 9]
"ababeabab"-> [0, 0, 1, 2, 0, 1, 2, 3, 4]
code 如下:
public static boolean isMultiple(String s){
if(s == null || s.length() == 0) {
throw new IllegalArgumentException("Bad input: input string
cannot be null or empty!");
}
int n = s.length();
if(n < 4) {
return false; //since the short string needs to have a length >=
2 and repeat at least once
}
int[] l = new int[n];
int j = 0;
l[0] = 0;
for(int i = 1; i < n; i++) {
while(j > 0 && s.charAt(i) != s.charAt(j)) {
j = l[j-1];
}
if(s.charAt(i) == s.charAt(j)) {
j++;
}
l[i] = j;
}
System.out.println(Arrays.toString(l));
int len = n-l[n-1];
return len > 1 && l[n-1]/len >= 1 && l[n-1]%len == 0;
}

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

p********r
发帖数: 66
159
把字符串看成一个环,用一个下标 i 指向新的字符串的开始位置
i = 2 to n/2 i = k表示pattern的长度是k
i = k 时判断 i%k == 0 并且从k开始的新字符串等于从0开始的字符串(字符串比较可
以in place实现)
如果条件不符合则 i++
比如:
str1 = abcabcabc
i = 2, str2 = cabcabcab 9%2 != 0 => i++
i = 3, str2 = abcabcabc 9%3 == 0 and str2 == str1 => return true
比如:
str1 = bcdbcdbcde
i = 2, str2 = dbcdbcdebc 10 %2 == 0 but str1 != str2 => i++
i = 3, str2 = bcdbcdebcd 10 %3 != 0 => i++
i = 4, similar to i =3
i = 5, str2 = dbcdebcdbc str1 != str2 => return false
aaaaaaaaaa 应该返回True吧 ,我们可以把重复字串看成是aa或aaaaa啊
T*****u
发帖数: 7103
160
ABABCABABC不行啊

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

相关主题
查找substr的问题finds all repeated substrings in the string --- YAHOO interview question
Longest common string问题还真从来没见过考KMP之类string matching算法的
问几道较难的字符串题storm8 online test 讨论
进入JobHunting版参与讨论
T*****u
发帖数: 7103
161
我能想到的方法就是对长度做因数分解,然后做因数长度string的match
r**********g
发帖数: 22734
162
当作string matching是一个思路,还有个比较好玩的思路,就是当成一个波来做傅里
叶变换, DFT的复杂度是N log N。变换以后频率最小的那个峰就是pattern的长度。
i*********n
发帖数: 58
163
bool isMultiple(string s)
{
if (s.size() < 2)
return false;
int right = 0;
int match = 0;
for(int i = 1; i < s.size(); ++ i)
{
if (s[i] == s[match]) {
if (match++ == right)
match = 0;
}
else
right = i;
}
return (right != 0 && right != ((int)s.size() - 1));
}
T*****u
发帖数: 7103
164
这个false positive太多

【在 r**********g 的大作中提到】
: 当作string matching是一个思路,还有个比较好玩的思路,就是当成一个波来做傅里
: 叶变换, DFT的复杂度是N log N。变换以后频率最小的那个峰就是pattern的长度。

z******g
发帖数: 271
165
确实
We can build the partial match table in one scan:
abc abc abc abc
000 123 456 789
Few line of c:
int asdasd(const char *s)
{
int len = strlen(s);
int *pmt = (int *)malloc(sizeof(int) * len);
int match = 0, i;
for(i = 1; i < len; ++ i)
{
if(s[i] == s[match])
pmt[i] = ++ match;
else
pmt[i] = match = 0;
}
int pattern_len = 0;
while(pattern_len < len && pmt[pattern_len] == 0)
++ pattern_len;
int repeat = pmt[len - 1];
return pattern_len > 1 &&
pattern_len + repeat == len &&
repeat % pattern_len == 0;
}

【在 p*****2 的大作中提到】
: KMP吧。
b****f
发帖数: 138
166
Mark
u*****o
发帖数: 1224
167
这个答案很不错,想问问
如果head>= len则归零
这个条件什么时候为true呢? head会比len大吗?

【在 c****p 的大作中提到】
: 两个指针,head, tail,记循环节长度len为1
: head初始都为0,tail为1。tail一直自增。
: 如果str[head] == str[tail], head自增。如果head>= len则归零
: 如果str[head] != str[tail],则len = tail。
: 扫完一遍查len和str.size()的关系就得了。

l*****i
发帖数: 13
168
abaaabaa False
想不出来只扫一遍的做法啊

【在 a*s 的大作中提到】
: 扫描一次
: #include
: #include
: using namespace std;
: const int min_len = 2;
: bool is_multiple (string s) {
: int r = s.length() - 1;
: int t = s.length() - 1 - min_len;
: int l = min_len;
: while (t >= 0 && l <= s.length() / 2) {

c****p
发帖数: 6474
169
会啊。
ababababababab这种情况Len=2

【在 u*****o 的大作中提到】
: 这个答案很不错,想问问
: 如果head>= len则归零
: 这个条件什么时候为true呢? head会比len大吗?

t*****a
发帖数: 106
170
你这个就是27楼beewmf的算法,最多是amortized的O(n),还是要回溯的。

【在 c****p 的大作中提到】
: 两个指针,head, tail,记循环节长度len为1
: head初始都为0,tail为1。tail一直自增。
: 如果str[head] == str[tail], head自增。如果head>= len则归零
: 如果str[head] != str[tail],则len = tail。
: 扫完一遍查len和str.size()的关系就得了。

相关主题
storm8 online test 讨论我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印
问一道n-ary tree 的题目问一个Pinterest的题目
求教电面遇到的一道pattern match的实现问个google老题的最佳解法
进入JobHunting版参与讨论
A****L
发帖数: 138
171
贴一个 O(n) 解法, java code 用了KMP 里的prefix function. 思路是前面有人提到
的 topcoder连接里讲解的。
public boolean checkRepetition(String s) {
int m = s.length();
if(m<4) return false;
for(int i=1;i if(s.charAt(i)!=s.charAt(i-1)) break;
if(i==m-1) return false;
}
int[] pattern = prefixFunction(s);
int p = pattern[m];
while(p>1) {
if(p%(m-p)==0) return true;
p=pattern[p];
}
return false;
}

public int[] prefixFunction(String p) {
int m = p.length();
int [] next = new int[m+1];
next[0]=next[1]=0;
int k=0;
for(int q = 2;q<=m;q++) {
while(k>0 && p.charAt(q-1)!=p.charAt(k))
k=next[k];
if(p.charAt(k)==p.charAt(q-1))
k=k+1;
next[q] = k;
}
return next;
}


【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

x*****0
发帖数: 452
172
mark
m*****i
发帖数: 10
173
public boolean isMultiple(String s) {
if(s==null || s.length()==0)
return true;
int maxInterval = 1;
HashMap map = new HashMap();
char[] chs = s.toCharArray();
for(int i=0; i if(!map.containsKey(chs[i]))
map.put(chs[i], i);
else{
int pre = map.get(chs[i]);
if(maxInterval<(i-pre)){
maxInterval = i-pre;
}
map.put(chs[i], i);
}
}
int length = chs.length;
if(maxInterval==1){
if(length%2==0 && length/2>1)
return true;
for(int i=3; i*i<=length; i+=2){
if(length%i==0 && length/i>1)
return true;
}
return false;
}
if(length%maxInterval!=0)
return false;
List list = new ArrayList();
for(int i=0; i list.add(s.substring(i, i+maxInterval));
if(list.size()==1)
return false;
String pre = list.get(0);
for(String str : list){
if(!pre.equals(str))
return false;
}
return true;
}
Test case:
"abcabcabcab" // false
"bcdbcdbcde" //false
"abcdabcd" //true
"xyzxy" //false
"aaaaaaaaaaaaaaaaaaaaa" //true
"bcdbcdbcdbcdbcdbc" //fasle
"aaaaabaaaa" //false
bcdbcdbcdebcdbcdbcde //true

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

c*******2
发帖数: 60
174
Given String S of length n. Return false if n < 4.
Let T = S.substring(1) + S.substring(0,n-1), return true if S is substring
of T
If "aaaaaaaaaa" is False, then return T.indexOf(S) > 0

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

r****7
发帖数: 2282
175
challenge me
bool isRepeat(string s) {
bool ret = false;
int sz = s.size();
vector pi(sz, 0);
int k = 0;
for (int i = 1; i < sz; i ++) {
while (k != 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k ++;
}
pi[i] = k;
}
int d = sz - pi[sz - 1];

int idx = d - 1;
int expectedRes = 0;

bool rFlag = false;
if (d < 2) {
ret = false;
goto e;
}
while (true) {
if (idx == sz - 1) {
ret = rFlag;
goto e;
}
if (idx >= sz) {
ret = false;
goto e;
}
if (pi[idx] != expectedRes) {
ret = false;
goto e;
} else {
idx += d;
expectedRes += d;
}
rFlag = true;
}
e:
printf("string %s ret is %d.\n", s.c_str(), ret);
return ret;
}
int main() {
bool ret = isRepeat("abcabcabc");
ret = isRepeat("bcdbcdbcde");
ret = isRepeat("abcdabcd");
ret = isRepeat("xyz");
ret = isRepeat("aaaaaaaaaa");
ret = isRepeat("aaaba");
ret = isRepeat("aaaba aaaba");
ret = isRepeat("ababeabab");
return 0;
}

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

p**p
发帖数: 742
176
这题用KMP吧。检查preprocess部分生产的array l 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件:
1. l[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-l[n-1])就是repeating pattern;
3. l[n-1]/(length of the repeating pattern) >= 1;
4. l[n-1] % (length of the repeating pattern) == 0.
比如:
"abcabcabc" -> [0, 0, 0, 1, 2, 3, 4, 5, 6]
"abcdabcd"-> [0, 0, 0, 0, 1, 2, 3, 4]
几个false cases:
"bcdbcdbcdebcdbcdbcd" -> [0, 0, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7,
8, 9]
"ababeabab"-> [0, 0, 1, 2, 0, 1, 2, 3, 4]
code 如下:
public static boolean isMultiple(String s){
if(s == null || s.length() == 0) {
throw new IllegalArgumentException("Bad input: input string
cannot be null or empty!");
}
int n = s.length();
if(n < 4) {
return false; //since the short string needs to have a length >=
2 and repeat at least once
}
int[] l = new int[n];
int j = 0;
l[0] = 0;
for(int i = 1; i < n; i++) {
while(j > 0 && s.charAt(i) != s.charAt(j)) {
j = l[j-1];
}
if(s.charAt(i) == s.charAt(j)) {
j++;
}
l[i] = j;
}
System.out.println(Arrays.toString(l));
int len = n-l[n-1];
return len > 1 && l[n-1]/len >= 1 && l[n-1]%len == 0;
}

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

p********r
发帖数: 66
177
把字符串看成一个环,用一个下标 i 指向新的字符串的开始位置
i = 2 to n/2 i = k表示pattern的长度是k
i = k 时判断 i%k == 0 并且从k开始的新字符串等于从0开始的字符串(字符串比较可
以in place实现)
如果条件不符合则 i++
比如:
str1 = abcabcabc
i = 2, str2 = cabcabcab 9%2 != 0 => i++
i = 3, str2 = abcabcabc 9%3 == 0 and str2 == str1 => return true
比如:
str1 = bcdbcdbcde
i = 2, str2 = dbcdbcdebc 10 %2 == 0 but str1 != str2 => i++
i = 3, str2 = bcdbcdebcd 10 %3 != 0 => i++
i = 4, similar to i =3
i = 5, str2 = dbcdebcdbc str1 != str2 => return false
aaaaaaaaaa 应该返回True吧 ,我们可以把重复字串看成是aa或aaaaa啊
T*****u
发帖数: 7103
178
ABABCABABC不行啊

pattern

【在 z******h 的大作中提到】
: 直接扫一遍就可以了吧,维护一个pattern的字符串,发现匹配不上的时候就把pattern
: 更新为从第一个字符到当前字符的字符串,并且从当前字符开始重新匹配。因为原来字
: 符串的开头必然是pattern的开头,并没有必要KMP。
:
: ★ 发自iPhone App: ChineseWeb 7.8
: ★ 发自iPhone App: ChineseWeb 7.8

T*****u
发帖数: 7103
179
我能想到的方法就是对长度做因数分解,然后做因数长度string的match
r**********g
发帖数: 22734
180
当作string matching是一个思路,还有个比较好玩的思路,就是当成一个波来做傅里
叶变换, DFT的复杂度是N log N。变换以后频率最小的那个峰就是pattern的长度。
相关主题
G onsite题求讨论F面经的一题
Interleave Strings那个题目有O(n)时间 O(1)空间算法么?没啥乐趣了
FB面试题一道 求解问一个KMP算法的问题
进入JobHunting版参与讨论
i*********n
发帖数: 58
181
bool isMultiple(string s)
{
if (s.size() < 2)
return false;
int right = 0;
int match = 0;
for(int i = 1; i < s.size(); ++ i)
{
if (s[i] == s[match]) {
if (match++ == right)
match = 0;
}
else
right = i;
}
return (right != 0 && right != ((int)s.size() - 1));
}
T*****u
发帖数: 7103
182
这个false positive太多

【在 r**********g 的大作中提到】
: 当作string matching是一个思路,还有个比较好玩的思路,就是当成一个波来做傅里
: 叶变换, DFT的复杂度是N log N。变换以后频率最小的那个峰就是pattern的长度。

z******g
发帖数: 271
183
确实
We can build the partial match table in one scan:
abc abc abc abc
000 123 456 789
Few line of c:
int asdasd(const char *s)
{
int len = strlen(s);
int *pmt = (int *)malloc(sizeof(int) * len);
int match = 0, i;
for(i = 1; i < len; ++ i)
{
if(s[i] == s[match])
pmt[i] = ++ match;
else
pmt[i] = match = 0;
}
int pattern_len = 0;
while(pattern_len < len && pmt[pattern_len] == 0)
++ pattern_len;
int repeat = pmt[len - 1];
return pattern_len > 1 &&
pattern_len + repeat == len &&
repeat % pattern_len == 0;
}

【在 p*****2 的大作中提到】
: KMP吧。
b****f
发帖数: 138
184
Mark
f**********t
发帖数: 1001
185
// 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至
少为 2,输入一个String写代码返回T或者F
bool isMultiple(string s) {
size_t i = 1;
while (i < s.size() && s[i] == s[0]) {
++i;
}
++i;
size_t dupLength = i;
while (i < s.size()) {
if (i + dupLength > s.size()) {
return false;
}
if (s[i] == s[0]) {
size_t k = 0;
for (; k < dupLength; ++k) {
if (s[k] != s[i + k]) {
dupLength = i + k + 1;
break;
}
}
if (i + k == s.size()) {
return true;
}
if (k == dupLength) {
i = i + k;
} else {
i = i + k + 1;
}
} else {
dupLength = i + 1;
++i;
}
}
return false;
}
void isMultipleTest() {
cout << "isMultiple: " << isMultiple("abcabcabc")
<< ' ' << isMultiple("bcdbcdbcde") << ' ' << isMultiple("abcdabcd")
<< ' ' << isMultiple("xyz") << ' ' << isMultiple("aaaa") << endl;
}
y*****h
发帖数: 22
186
public boolean isMultipleDuplicate(String s) {
int patternPos = 0, patternEnd = 0;
for(int i=1; i if(s.charAt(i) != s.charAt(patternPos)) {
patternPos = 0;
patternEnd = i;
} else {
if(++patternPos > patternEnd && i != s.length()-1) {
patternPos = 0;
}
}
}
return patternPos>patternEnd && patternEnd>0;
}
Result:
abcabcabc: true
bcdbcdbcde: false
abcdabcd: true
xyzxy: false
aaaaaaaaaa: false
ABABCABABC: true
bcdbcdbcdebcdbcdbcde: true
ababeabab: false
ababab: true
bcdbcdbcdbcdbcdbc: false
abcabcabcab: false
p*****9
发帖数: 273
187
mark
Z**n
发帖数: 55
188
Mark 下
j****1
发帖数: 99
189
haonan....
l*****8
发帖数: 1083
190
mark
相关主题
微软电面Longest common string问题
问2道面试题问几道较难的字符串题
查找substr的问题finds all repeated substrings in the string --- YAHOO interview question
进入JobHunting版参与讨论
C****t
发帖数: 53
191
Python
def find(self, string):
length = len(string)
for i in range(1, length//2+1):
if string[i] == string[-1] and length % (i+1) == 0 and \
string[:(i+1)] * (length // (i+1)) == string:
return True
return False
l*********o
发帖数: 3091
192
其实就brut force.基本O(n).不符合的很快就return,写起来也简单。
bool BrutForceCheck(char* str, int sub, int n)
{
if (n / sub*sub != n) return false;
int m = n / sub;
if (m < 2) return false;
int k;
for (int i = 1; i < m; i++)
{
k = i*sub;
for (int j = 0; j < sub; j++)
{
if (str[k + j] != str[j]) return false;
}
}
return true;
}
bool CheckIfStrHasInternalRepeat(char* str)
{
bool rtn = false;
int length = strlen(str);
for (int i = 2; i <= length / 2; i++)
{
if (BrutForceCheck(str, i, length))
{
rtn = true;
break;
}
}
return rtn;
}
c***t
发帖数: 50
193
当前不匹配的char需要和首字母比较是个好办法
p*****9
发帖数: 273
194
mark
c*******f
发帖数: 85
195
aaaaa ?

【在 l*****4 的大作中提到】
: 贡献一下我的,试过大家提到的所有case, 都可以
: 利用string本身作为pattern
: 如果前半部分都match的话,指针要过中点
: 只判断是否过中点的话,“aaaaabaaaa”这种就判断错误
: 是因为后一段短,从指针到pattern结束的位置没有被扫到
: 如果把指针到string 末尾的再和string前一部分相同长度的段对比,如果是重复,那
: 就真的是true
: 如果没办法重复,就说明漏扫了不同的部分,false
: 解释的可能不清楚,还是看代码吧,java
: public boolean isMultiple(String s) {

s***o
发帖数: 4
196
发一个我的见解,欢迎指正!
#Construct the partial match table of the KMP algorithm for the whole string
to solve this problem.
def repeat_substring(ss):
n = len(ss)
#construct the partial match table in O(n) time
T = [-1] * (n + 1)
for i in range(1,n+1):
pos = T[i-1]
while pos != -1 and ss[pos] != ss[i-1]:
pos = T[pos]
T[i] = pos + 1
#check the maximum length of matched proper suffix and proper prefix of
the whole string
if T[n] < 2:
return False
m = n - T[n]
return True if m != 1 and T[n] % m == 0 else False
m*******g
发帖数: 410
197
貌似很简洁,解释一下吧。

【在 y*****h 的大作中提到】
: public boolean isMultipleDuplicate(String s) {
: int patternPos = 0, patternEnd = 0;
: for(int i=1; i: if(s.charAt(i) != s.charAt(patternPos)) {
: patternPos = 0;
: patternEnd = i;
: } else {
: if(++patternPos > patternEnd && i != s.length()-1) {
: patternPos = 0;
: }

m*******g
发帖数: 410
198
这个想法貌似很正确,直接有效。

【在 m*****n 的大作中提到】
: 有一个思路,
: 首先把字符串统计字符个数 O(1),比如,
: “abaabaabac”
: 就是6个a, 3个b, 1个c,所以不肯能,因为1个c不能被分组。
: 如果"abaabaabacc", 6个a, 3个b, 2个c,不可能被分组,因为,3个b和2个c没有公因
: 数。
: 如果"abaabaabaccc", 6个a, 3个b, 3个c,只能分3组,但明显不成立。O(n)。
: 对于单一字符,直接return false,
: 对于"abaabaabaaba",有8个a,4个b,能被分4或2组,分4组成立,2组也行。。
: 这个算法的麻烦在于如果最大公因数太大,比如有10000个a, 5000个b。最大公因数是

z***y
发帖数: 73
199
写得真好!值得学习。
还可以加判断:patternEnd > s.length() / 2,走过一半就可以结束了;
以及 s.length() % (patternEnd + 1) != 0, ++i, ++patternEnd,过滤掉长度不符合
的情况。

【在 y*****h 的大作中提到】
: public boolean isMultipleDuplicate(String s) {
: int patternPos = 0, patternEnd = 0;
: for(int i=1; i: if(s.charAt(i) != s.charAt(patternPos)) {
: patternPos = 0;
: patternEnd = i;
: } else {
: if(++patternPos > patternEnd && i != s.length()-1) {
: patternPos = 0;
: }

l****4
发帖数: 27
200
mark一下
相关主题
还真从来没见过考KMP之类string matching算法的求教电面遇到的一道pattern match的实现
storm8 online test 讨论我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印
问一道n-ary tree 的题目问一个Pinterest的题目
进入JobHunting版参与讨论
z*******o
发帖数: 4773
201
up
f*****i
发帖数: 835
202
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt
1. build "Partial match" table.
2. can tell from the string size and last number of the table.
bool isMultiple(std::vector t){
if(t.size()<4) return false;
int repeat_part = t[t.size()-1]+1;
int non_repeat_part = t.size()-repeat_part;
if(non_repeat_part < 2) return false;
if(repeat_part < non_repeat_part) return false;
if((repeat_part%non_repeat_part)!=0) return false;
return true;
}

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

i*********e
发帖数: 21
203
53楼的topcoder turtorial是正解。
y*****h
发帖数: 22
204
嗯,你说的很对。这些条件加上后可以快速过滤很多不符合的情况。我记下了。

【在 z***y 的大作中提到】
: 写得真好!值得学习。
: 还可以加判断:patternEnd > s.length() / 2,走过一半就可以结束了;
: 以及 s.length() % (patternEnd + 1) != 0, ++i, ++patternEnd,过滤掉长度不符合
: 的情况。

y*****h
发帖数: 22
205
patternPos表示从哪里开始匹配。初始值为0。
patternEnd表示模式结束的位置。初始值为0。
当前字符和patternPos不相等的话,说明pattern不成立,patternPos回到开始位置0,
patternEnd设为当前字符所在位置i。
当前字符和patternPos相等的话,patternPos加1移到下一个位置,patternEnd保持不
变。并检查下如果patternPos超过patternEnd的话,说明截止到当前字符成功匹配,
patternPos回到开始开始匹配下一串字符。注意,当i走到最后的话,patternPos就不
用清0了。
最后判断成功的条件是,patternPos大于patternEnd的时候,说明整个字符串pattern
且至少重复pattern两次。patternEnd大于零,说明pattern长度大于1。

【在 m*******g 的大作中提到】
: 貌似很简洁,解释一下吧。
S*******C
发帖数: 822
206
mark

pattern

【在 y*****h 的大作中提到】
: patternPos表示从哪里开始匹配。初始值为0。
: patternEnd表示模式结束的位置。初始值为0。
: 当前字符和patternPos不相等的话,说明pattern不成立,patternPos回到开始位置0,
: patternEnd设为当前字符所在位置i。
: 当前字符和patternPos相等的话,patternPos加1移到下一个位置,patternEnd保持不
: 变。并检查下如果patternPos超过patternEnd的话,说明截止到当前字符成功匹配,
: patternPos回到开始开始匹配下一串字符。注意,当i走到最后的话,patternPos就不
: 用清0了。
: 最后判断成功的条件是,patternPos大于patternEnd的时候,说明整个字符串pattern
: 且至少重复pattern两次。patternEnd大于零,说明pattern长度大于1。

a*****2
发帖数: 96
207
// KMP preprocessing
public static boolean isMultiple(String s){
int[] arr = new int[s.length()];
Arrays.fill(arr,0);
for(int i = 1; i < s.length(); i++)
if(s.charAt(i) == s.charAt(arr[i-1]))
arr[i] = arr[i-1]+1;

String patten = "";

// "aaaaa"
if(arr[s.length()-1] == s.length() - 1){
int steps = 3;
int n = s.length();
while(steps <= n/2)
if(n%steps == 0)
return true;
else
steps++;

return false;
}
else
patten = arr[s.length()-1] == 0? s.substring(0,1): s.
substring(arr[s.length()-1]);
int step = s.length() - arr[s.length()-1];
int start = 0;

while(start < s.length()){
if(!s.substring(start,start+step).equalsIgnoreCase(patten))
return false;
start += step;
}

return true;

}
m*******g
发帖数: 410
208
谢谢大牛

:patternPos表示从哪里开始匹配。初始值为0。
:patternEnd表示模式结束的位置。初始值为0。
o*****e
发帖数: 379
209
mark
c***m
发帖数: 11
210
mark
这个A家是airbnb吗?
相关主题
问一个Pinterest的题目Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
问个google老题的最佳解法FB面试题一道 求解
G onsite题求讨论F面经的一题
进入JobHunting版参与讨论
c******1
发帖数: 37
211
双指针的好像不太对, 比如长度n的时候发现不行, 你直接就去检查长度n + 1了,似
乎没法证明在0 - n中没有其他可能

pattern

【在 y*****h 的大作中提到】
: patternPos表示从哪里开始匹配。初始值为0。
: patternEnd表示模式结束的位置。初始值为0。
: 当前字符和patternPos不相等的话,说明pattern不成立,patternPos回到开始位置0,
: patternEnd设为当前字符所在位置i。
: 当前字符和patternPos相等的话,patternPos加1移到下一个位置,patternEnd保持不
: 变。并检查下如果patternPos超过patternEnd的话,说明截止到当前字符成功匹配,
: patternPos回到开始开始匹配下一串字符。注意,当i走到最后的话,patternPos就不
: 用清0了。
: 最后判断成功的条件是,patternPos大于patternEnd的时候,说明整个字符串pattern
: 且至少重复pattern两次。patternEnd大于零,说明pattern长度大于1。

S*******C
发帖数: 822
212
我的最优解,目前最精简解法,未发现任何问题
public class Solution {
//two pointers patternPos & patternEnd
public boolean isMultipleDuplicate(String s) {
int patternPos = 0, patternEnd = 1;
for (int i = 1; i < s.length() && patternEnd <= s.length() / 2; i++)
{
if (s.length() % (patternEnd + 1) != 0)
patternEnd++;// 过滤掉长度不符合的情况
//if s[i] != s[patternPos], reset the pattern
else if (s.charAt(i) != s.charAt(patternPos)) {
patternPos = 0;
patternEnd = i;
//else if s[i] == s[patternPos], we increment the patternPos so
that we can compare s[i+1] with s[patternPos+1] in the next iteration
// if we find patternPos > patternEnd, the current
patternPos is illegal, reset it to 0
} else if (++patternPos > patternEnd && i != s.length() - 1)
patternPos = 0;
}
//if s is is composed of multiple duplicate string, then patternPos
== patternEnd +1
return patternPos == patternEnd + 1;
}
public static void main(String args[]){
String[] strs = {
"xyxy",//xy, true
"abcabc",//abc, true
"abcabcabc",//abc, true
"abcdabcd",//abcd, true
"ABABCABABC",//ABABC, true
"bcdbcdbcdebcdbcdbcde", //bcdbcdbcde, true
"ababab",//ab, true
"12341234",//1234, true
"123412341234",//1234, true
"1234512345",//12345, true
"123451234512345",//12345, true
"113451134511345",//12345, true
"13311331",//1331, true
"112112112",//112, true
"11121112",//1112, true

"ababeabab",//false
"bcdbcdbcdbcdbcdbc",//false
"abcabcabcab",//false
"abcabcabcX",//false
"bcdbcdbcde",//false
"xyzxy",//false
"aaaaaaaaaa",//false
"a",//false
"aa",//false
"aaa",//false
"xyz",//false
"aabbccdd",//false
"13311331331",//false
"1112111211"//false
};
for(String s: strs)
System.out.println(s + "\t" + new Solution().isMultipleDuplicate
(s));
}
}
S*******C
发帖数: 822
213
不好意思,刚想出来一个超级精简的解法
public class Solution {
//two pointers patternPos & patternEnd
public boolean isMultipleDuplicate(String s) {
int patternPos = 0, patternEnd = 1;
for (int i = 1; i < s.length() && patternEnd <= s.length() / 2; i++){
// 过滤掉长度不符合以及不匹配的情况
if (s.length() % (patternEnd + 1) != 0 || s.charAt(i) != s.
charAt(patternPos)){
patternPos = 0;
patternEnd = i;
//else if s[i] == s[patternPos], we increment the patternPos so
that we can compare
//s[i+1] with s[patternPos+1] in the next iteration
//if we find patternPos > patternEnd, then we reset patternPos
to compare the next iteration of the pattern
} else if (++patternPos > patternEnd && i != s.length() - 1)
patternPos = 0;
}

return patternPos == patternEnd + 1;
}
public static void main(String args[]){
String[] strs = {
"xyxy",//xy, true
"abcabc",//abc, true
"abcabcabc",//abc, true
"abcdabcd",//abcd, true
"ABABCABABC",//ABABC, true
"bcdbcdbcdebcdbcdbcde", //bcdbcdbcde, true
"ababab",//ab, true
"12341234",//1234, true
"123412341234",//1234, true
"1234512345",//12345, true
"123451234512345",//12345, true
"113451134511345",//12345, true
"13311331",//1331, true
"112112112",//112, true
"11121112",//1112, true
"a",//false
"aa",//false
"aaa",//false
"aaaa",//false
"aaaaa",//false
"aaaaaa",//false
"aaaaaaa",//false
"aaaaaaaa",//false
"ababeabab",//false
"bcdbcdbcdbcdbcdbc",//false
"abcabcabcab",//false
"abcabcabcX",//false
"bcdbcdbcde",//false
"xyzxy",//false
"aaaaaaaaaa",//false
"xyz",//false
"aabbccdd",//false
"13311331331",//false
"1112111211"//false
};
for(String s: strs)
System.out.println(s + "\t" + new Solution().isMultipleDuplicate
(s));
}
}
f*******b
发帖数: 520
214
关键在于简单易懂:
public static boolean isMultiple(String s) {
if (s == null || s.length() < 4) return false;
String p = s.substring(0, 1);
int times = 1;
for (int i = 1; i < s.length();) {
int j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
j++;
i++;
} else {
p = s.substring(0, i+1);
i++;
break;
}
}
if (j == p.length()) {
times++;
} else {
times = 1;
}
}

if (p.length() <= 1 || times <= 1) return false;

return true;
}
W***o
发帖数: 6519
215
以前用Turing machine设计解决这种题的方法,呵呵,无非就是扫描,假设string
pattern,验证。。

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

f*******r
发帖数: 976
216
LZ不用多放在心上,这道题不简单啊。这道题考的是对KMP的理解深度,最主要的就是
考的KMP里面的计算pattern string的next矩阵的计算方法。如果一个string是由一个
substring重复多次拼接而成,那么它的next矩阵肯定是这样:
x x x 3 4 5 6 7 8 9 ...
也就是说,next矩阵的后半部分一定是一个递增的数列。通过这个next矩阵我们就可以
计算出那个substring的长度,然后再来计算整个数组是不是这个substring的倍数,比
如abcdabcdabc虽然是重复多次,但是最后那个重复是abc,没有完整,少了个d。对于
KMP的理解,这篇博文写得不错:http://blog.csdn.net/v_july_v/article/details/7041827
我也来贴两个解法,第一个解法是暴力解法,从左到右扫描,如果找到了那个重复的
substring,就用这个substring来继续match整个string。如果不成功,那么就继续找
那个substring,不回溯,只是比较次数多,时间复杂度不是O(n),而是O(n^2).
// Return true if the substr s[0..idx-1] matches s[idx..2*idx-1].
bool match(const string &s, int idx) {
const int n = s.size();
for (int i = 0; i < idx; ++i) {
if (idx+i >= n || s[i] != s[idx+i]) return false;
}
return true;
}
// Brute-force.
bool isDuplicate(string s) {
int end = -1;
for (int i = 1, e = s.size(); i < e; ++i) {
if (end == -1) {
if (match(s, i)) end = i;
} else {
if (s[i] != s[i%end]) end = -1;
}
}
return end != -1 && end != 1 && (s.size()%end == 0);
}
第二个解法就是上面讲到的用KMP的计算pattern string的next array的方法,时间复
杂度是O(n).
bool isDuplicate2(string s) {
const int n = s.size();
if (n < 3) return false;
vector next(n, 0);
next[0] = -1;
int k = -1, i = 0;
// Compute the next array of KMP pattern string.
// http://blog.csdn.net/v_july_v/article/details/7041827
while (i < n-1) {
if (k == -1 || s[k] == s[i]) {
k++, i++;
next[i] = k;
} else
k = next[k];
}
// Check whether there is any repetition.
if (next[n-1] < n/2 - 1) return false;
// Check whether the last part of the array is an increasing sequence.
// i is the length of the repeated substring. For example, s:"abcabc" -> i
:3
for (i = n-2; i >= 0; --i) {
if (next[i] != next[i+1]-1 || next[i] == 0) break;
}
// Check whether s is the multiple of the substring.
if (i <= 1 || n % i != 0) return false;
return true;
}

有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
2,输入一个String写代码返回T或者F
例子:
"abcabcabc" Ture 因为它把abc重复3次构成
"bcdbcdbcde" False 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" False 因为它不是某一个String重复
"aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
要求算法复杂度为O(n)
public boolean isMultiple(String s){
}
一紧张,大脑一片空白,直接不会做!!!

【在 m*********1 的大作中提到】
: 有一种String,是把一个更短的String重复n次而构成的,那个更短的String长度至少为
: 2,输入一个String写代码返回T或者F
: 例子:
: "abcabcabc" Ture 因为它把abc重复3次构成
: "bcdbcdbcde" False 最后一个是bcde
: "abcdabcd" True 因为它是abcd重复2次构成
: "xyz" False 因为它不是某一个String重复
: "aaaaaaaaaa" False 重复的短String长度应至少为2(这里不能看做aa重复5次)
: 要求算法复杂度为O(n)
: public boolean isMultiple(String s){

S*******C
发帖数: 822
217
我的双指针解法就是O(N), 因为每一步i都会递增,递增n/2次
public boolean isMultipleDuplicate(String s) {
int patternPos = 0, patternEnd = 1;
for (int i = 1; i < s.length() && patternEnd <= s.length() / 2; i++){
// 过滤掉长度不符合以及不匹配的情况
if (s.length() % (patternEnd + 1) != 0 || s.charAt(i) != s.
charAt(patternPos)){
patternPos = 0;
patternEnd = i;
//else if s[i] == s[patternPos], we increment the patternPos so
that we can compare
//s[i+1] with s[patternPos+1] in the next iteration
//if we find patternPos > patternEnd, then we reset patternPos
to compare the next iteration of the pattern
} else if (++patternPos > patternEnd && i != s.length() - 1)
patternPos = 0;
}

return patternPos == patternEnd + 1;
}

【在 f*******r 的大作中提到】
: LZ不用多放在心上,这道题不简单啊。这道题考的是对KMP的理解深度,最主要的就是
: 考的KMP里面的计算pattern string的next矩阵的计算方法。如果一个string是由一个
: substring重复多次拼接而成,那么它的next矩阵肯定是这样:
: x x x 3 4 5 6 7 8 9 ...
: 也就是说,next矩阵的后半部分一定是一个递增的数列。通过这个next矩阵我们就可以
: 计算出那个substring的长度,然后再来计算整个数组是不是这个substring的倍数,比
: 如abcdabcdabc虽然是重复多次,但是最后那个重复是abc,没有完整,少了个d。对于
: KMP的理解,这篇博文写得不错:http://blog.csdn.net/v_july_v/article/details/7041827
: 我也来贴两个解法,第一个解法是暴力解法,从左到右扫描,如果找到了那个重复的
: substring,就用这个substring来继续match整个string。如果不成功,那么就继续找

f*******r
发帖数: 976
218
对的,你的也是O(n)

我的双指针解法就是O(N), 因为每一步i都会递增,递增n/2次
public boolean isMultipleDuplicate(String s) {
int patternPos = 0, patternEnd = 1;
for (int i = 1; i < s.length() && patternEnd <= s.length() / 2; i++){
// 过滤掉长度不符合以及不匹配的情况
if (s.length() % (patternEnd + 1) != 0 ||
s.charAt(i) != s.charAt(patternPos)) {
patternPos = 0;
patternEnd = i;
//else if s[i] == s[patternPos], we increment the patternPos
//so that we can compare
//s[i+1] with s[patternPos+1] in the next iteration
//if we find patternPos > patternEnd, then we reset patternPos
//to compare the next iteration of the pattern
} else if (++patternPos > patternEnd && i != s.length() - 1)
patternPos = 0;
}
return patternPos == patternEnd + 1;
}

【在 S*******C 的大作中提到】
: 我的双指针解法就是O(N), 因为每一步i都会递增,递增n/2次
: public boolean isMultipleDuplicate(String s) {
: int patternPos = 0, patternEnd = 1;
: for (int i = 1; i < s.length() && patternEnd <= s.length() / 2; i++){
: // 过滤掉长度不符合以及不匹配的情况
: if (s.length() % (patternEnd + 1) != 0 || s.charAt(i) != s.
: charAt(patternPos)){
: patternPos = 0;
: patternEnd = i;
: //else if s[i] == s[patternPos], we increment the patternPos so

s********5
发帖数: 6
219
我测试了一下你的代码
"abcababcababcab" 应该return true, 你的return false

+){
so

【在 S*******C 的大作中提到】
: 我的双指针解法就是O(N), 因为每一步i都会递增,递增n/2次
: public boolean isMultipleDuplicate(String s) {
: int patternPos = 0, patternEnd = 1;
: for (int i = 1; i < s.length() && patternEnd <= s.length() / 2; i++){
: // 过滤掉长度不符合以及不匹配的情况
: if (s.length() % (patternEnd + 1) != 0 || s.charAt(i) != s.
: charAt(patternPos)){
: patternPos = 0;
: patternEnd = i;
: //else if s[i] == s[patternPos], we increment the patternPos so

S*******C
发帖数: 822
220
谢谢指正,这题难度很大,上面这么多解法只有3种是对的
贴一种比较简洁的写法,不知道怎么证明是O(N)的解法?
public boolean isMultipleDuplicate(String s) {
if (s == null || s.length() < 4)
return false;
int len = s.length();
int[] a = new int[len];
int j = 0;
for (int i = 1; i < len; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j))
j = a[j - 1];
if (s.charAt(i) == s.charAt(j))
j++;
a[i] = j;
}
int patternLen = len - a[len - 1];
return patternLen > 1 && a[len - 1] / patternLen >= 1 && a[len - 1]
% patternLen == 0;
}

【在 s********5 的大作中提到】
: 我测试了一下你的代码
: "abcababcababcab" 应该return true, 你的return false
:
: +){
: so

相关主题
没啥乐趣了问2道面试题
问一个KMP算法的问题查找substr的问题
微软电面Longest common string问题
进入JobHunting版参与讨论
S*******C
发帖数: 822
221
这题所有的双指针解法都跪了,必须上KMP啊
z*********n
发帖数: 1451
222

Z数组这个确实很好,但是仁兄这里有点写错了把:
abcabcabc对应的Z应该是={null, 0, 0, 6, 0, 0, 3, 0, 0}
而判定条件也应该是z[i] + i == s.size() 吧?

【在 p******d 的大作中提到】
: 先用O(n)的Z algorithm算Z[i]=从i开始最长的prefix长度,i=1...n-1
: 例如
: abcabcabc对应的Z={null, 0, 0, 3, 0, 0, 3, 0, 0}
: aaabaaaaba对应的Z={null, 2, 1, 0, 3, 5, 2, 1, 0, 1}
: aaaaaaaaaa对应的Z={null, 9, 8, 7, 6, 5, 4, 3, 2, 1}
: 之后扫一遍Z数组返回满足Z[i]==i的i值,到i-1的prefix就是答案
: Z algorithm看这里http://codeforces.com/blog/entry/3107

l*****f
发帖数: 2198
223
想了一个晚上想出一个简便的解法:
1. 扫一遍string,统计每个字符出现的个数。
2. 如果是true,那每个字符出现的个数必定相等。所以如有任何字符出现次数与其他的
次数不符,返回false
3. 假设每个字符出现个数都为n,则“可能”会有符合条件的pattern. 此种pattern的
长度为
(string length/n)*i, i = 1,2,3,假设这个数为k
4. 写一个loop,依次验证
string(0) = string (k) = string (2k).....
string(1) = string(k+1) = string(2k + 1)...
...
直到string(k-1) = string(2k - 1) ...
任何时候遇到false,则返回结果false,否则返回true
复杂度没估计过,应该不会很大
l********e
发帖数: 3
224
这是我的思路,
1)假设输入字符串是s1, 长度为 N, 我们要找的重复的短字符串为result
2)一开始把result 设成s1的前两个字符。
3)引入两个索引变量i,j,i指向s1的字符,j指向result的字符。i=2, j=0
4)检查 s1[i] == result[j],如果成立,则j++;否则的话说明出现了mismatch,说明
result可能太短,需要扩展。扩展的字符应该是 s1[i-j,i],把这个扩展追加到result,
并且把j设置成0。
5)循环结束后检查result的长度和j是否相等,如果相等的话说明满足要求。当然还要
进一步确定result.size() == s1.size(),如果相等说名没有重复,返回false。
以下是不太严谨的的代码,
#include
#include
#include
#include
using namespace std;
bool isRepeated(string s1) {
size_t N = s1.size();
string result = s1.substr(0,2);
int j = 0;
for (int i = 2; i < N;i++) {
if (s1[i] == result[j])
j++;
else {
for (; j >= 0; j--) {
result.push_back(s1[i-j]);
}
j = 0;
}
}
return j == result.size();
}
int main() {
string s = "ababc";
bool result = isRepeated(s);
cout << "is " << s << " repeated? " << result << endl;
return 0;
}
l********e
发帖数: 3
225
这是我的思路,
1)假设输入字符串是s1, 长度为 N, 我们要找的重复的短字符串为result
2)一开始把result 设成s1的前两个字符。
3)引入两个索引变量i,j,i指向s1的字符,j指向result的字符。i=2, j=0
4)检查 s1[i] == result[j],如果成立,则j++;否则的话说明出现了mismatch,说明
result可能太短,需要扩展。扩展的字符应该是 s1[i-j,i],把这个扩展追加到result,
并且把j设置成0。
5)循环结束后检查result的长度和j是否相等,如果相等的话说明满足要求。当然还要
进一步确定result.size() == s1.size(),如果相等说名没有重复,返回false。
以下是不太严谨的的代码,
#include
#include
#include
#include
using namespace std;
bool isRepeated(string s1) {
size_t N = s1.size();
string result = s1.substr(0,2);
int j = 0;
for (int i = 2; i < N;i++) {
if (s1[i] == result[j])
j++;
else {
for (; j >= 0; j--) {
result.push_back(s1[i-j]);
}
j = 0;
}
}
return j == result.size();
}
int main() {
string s = "ababc";
bool result = isRepeated(s);
cout << "is " << s << " repeated? " << result << endl;
return 0;
}
l********e
发帖数: 3
226
这是我的思路,
1)假设输入字符串是s1, 长度为 N, 我们要找的重复的短字符串为result
2)一开始把result 设成s1的前两个字符。
3)引入两个索引变量i,j,i指向s1的字符,j指向result的字符。i=2, j=0
4)检查 s1[i] == result[j],如果成立,则j++;否则的话说明出现了mismatch,说明
result可能太短,需要扩展。扩展的字符应该是 s1[i-j,i],把这个扩展追加到result,
并且把j设置成0。
5)循环结束后检查result的长度和j是否相等,如果相等的话说明满足要求。当然还要
进一步确定result.size() == s1.size(),如果相等说名没有重复,返回false。
以下是不太严谨的的代码,
#include
#include
#include
#include
using namespace std;
bool isRepeated(string s1) {
size_t N = s1.size();
string result = s1.substr(0,2);
int j = 0;
for (int i = 2; i < N;i++) {
if (s1[i] == result[j])
j++;
else {
for (; j >= 0; j--) {
result.push_back(s1[i-j]);
}
j = 0;
}
}
return j == result.size();
}
int main() {
string s = "ababc";
bool result = isRepeated(s);
cout << "is " << s << " repeated? " << result << endl;
return 0;
}
d********y
发帖数: 2114
227
用KMP的next table
1.计算KMP的next table。这个是O(n)
2.如果有重复字符串组成,用输入字符串长度减去next table的最后一个值再减1,得
到重复字串的长度。
3.验证此子串长度大于1,子串最后一个字符和输入字符串最后一个字符相等,字符串
长度可以整除字串长度。
假设计算出的子串长度为p。根据next table的定义,对于0 <= i < i+p <= s.Length
- 1, s[i] = s[i + p]。这就是一个周期函数的表达式。
y***a
发帖数: 840
228
def loop(input):
if len(input) < 4:
#print input, False
return False
tmp_end = 1
cur_pattern_pos = 0
idx = 2
match = False
while idx < len(input):
char = input[idx]
if char == input[cur_pattern_pos]:
#print '----', char, cur_pattern_pos, tmp_end
cur_pattern_pos = (cur_pattern_pos+1)%(1+tmp_end)
idx += 1
match = True
else:
#print '====', char, cur_pattern_pos, tmp_end
if cur_pattern_pos == 0:
tmp_end = idx
idx += 1
else:
tmp_end = idx-1
cur_pattern_pos = 0
match = False
#print input, cur_pattern_pos == 0 and match
return cur_pattern_pos == 0 and match
F**********r
发帖数: 2
229
貌似不需要验证这步:“子串最后一个字符和输入字符串最后一个字符相等”。不知是
否正确。。。

Length

【在 d********y 的大作中提到】
: 用KMP的next table
: 1.计算KMP的next table。这个是O(n)
: 2.如果有重复字符串组成,用输入字符串长度减去next table的最后一个值再减1,得
: 到重复字串的长度。
: 3.验证此子串长度大于1,子串最后一个字符和输入字符串最后一个字符相等,字符串
: 长度可以整除字串长度。
: 假设计算出的子串长度为p。根据next table的定义,对于0 <= i < i+p <= s.Length
: - 1, s[i] = s[i + p]。这就是一个周期函数的表达式。

1 (共1页)
进入JobHunting版参与讨论
相关主题
查找substr的问题我想说,我的A家电面,绝对是被烙印黑了,两个45分钟两个烙印
Longest common string问题问一个Pinterest的题目
问几道较难的字符串题问个google老题的最佳解法
finds all repeated substrings in the string --- YAHOO interview questionG onsite题求讨论
还真从来没见过考KMP之类string matching算法的Interleave Strings那个题目有O(n)时间 O(1)空间算法么?
storm8 online test 讨论FB面试题一道 求解
问一道n-ary tree 的题目F面经的一题
求教电面遇到的一道pattern match的实现没啥乐趣了
相关话题的讨论汇总
话题: string话题: int话题: false话题: return话题: len