C***U
发帖数: 2406 | 1 The maximum suffix of a string is the lexicographically largest suffix of
the string. The maximum suffix problem is to find the maximum suffix of a
given string. Linear time algorithm required. |
f*****e
发帖数: 2992 | 2 给个O(N)的。
两个指针可以搞定。a[1...n]。
p1=a; // p1保存前i个元素的最大suffix的起始位置。
p2=a+1; // 当前扫到的位置，与以p1起始的字符串进行比较，分4种情况：
1)如果*p2>*p1，then p1=p2，
2)*p1==*p2, then p1++;p2++直到遇到比*p1,*p2都大的字符*p4，就p1=p4，p2=p4+1
3)*p1==*p2, strcmp(p1,p2)<0, p1=比较后的最后一个period;
4)*p2 < *p1, p2++;
while(p2 < a + n)
{
if(*p2 > *p1) p1 = p2;
else if(*p2 == *p1){
p4 = p2;
k = p2 - p1; // length of pattern or period a[p1...p2-1]
j = 1;
// repeatedly compare with a[p1...p2-1]
while(++p4 < a + n){
if(*p4 > *p1){
p2=p1=p4;
break;
}
else if(*p4 > *(p1 + j)){
p1=p4-j;
p2=p4;
break;
}else if(*p4 < *(p1 + j)){
p2=p4;
break;
}
j = (j+1)%k;
}
}
p2++;
}
return p1;
【在 C***U 的大作中提到】
: The maximum suffix of a string is the lexicographically largest suffix of
: the string. The maximum suffix problem is to find the maximum suffix of a
: given string. Linear time algorithm required.
|
C***U
发帖数: 2406 | 3 我不是很明白你的3)
这个例子怎么跑的？
cacacb
【在 f*****e 的大作中提到】
: 给个O(N)的。
: 两个指针可以搞定。a[1...n]。
: p1=a; // p1保存前i个元素的最大suffix的起始位置。
: p2=a+1; // 当前扫到的位置，与以p1起始的字符串进行比较，分4种情况：
: 1)如果*p2>*p1，then p1=p2，
: 2)*p1==*p2, then p1++;p2++直到遇到比*p1,*p2都大的字符*p4，就p1=p4，p2=p4+1
: 3)*p1==*p2, strcmp(p1,p2)<0, p1=比较后的最后一个period;
: 4)*p2 < *p1, p2++;
: while(p2 < a + n)
: {
|
f*****e
发帖数: 2992 | 4 3)就是caca < cacb，也就是strcmp('caca','cacb')<0，这种比较排除了第2种情况，
就是c之后没有比‘c'大的。所以p1一开始指第一个c，变成指第2个c。然后就结束了。
【在 C***U 的大作中提到】
: 我不是很明白你的3)
: 这个例子怎么跑的？
: cacacb
|
C***U
发帖数: 2406 | 5 但是最大应该是cb啊。。。。
变成
【在 f*****e 的大作中提到】
: 3)就是caca < cacb，也就是strcmp('caca','cacb')<0，这种比较排除了第2种情况，
: 就是c之后没有比‘c'大的。所以p1一开始指第一个c，变成指第2个c。然后就结束了。
|
C***U
发帖数: 2406 | 6 恩。我想了一个O(n)的，但是比你的复杂很多，空间也是O(n)的。关键是我觉得如果面
试的时候，现场不好写。你帮我看下对不对。
1） 找到字符串里面所有最大字母的位置，并且全部记录下来。
2） 然后看这些最大字符的后一位，还是找到最大的，并且把这些第二位也最大的记录
下来，然后给他们标记0，假设有k个标记0。把所有剩下的都标记为k，并且还记录这些
剩下的已经比较到哪个位置。这里第二位只过了2边。
3） 继续第二步，一直到找到一个唯一的最大字符串，或者有两个或以上的字符串遇到
下一个最大字符，那么就调用第二步记录的信息，看后一个最大字符串排名第几，如果
有一个唯一的排名最低，那么那个就是第一。如果不是唯一的，那么从第二步那里记录
的地方开始比较。
这样最后会结束比较，而且每个字符串只被比较了常数次。应该是4次吧。
【在 f*****e 的大作中提到】
: 3)就是caca < cacb，也就是strcmp('caca','cacb')<0，这种比较排除了第2种情况，
: 就是c之后没有比‘c'大的。所以p1一开始指第一个c，变成指第2个c。然后就结束了。
|
f*****e
发帖数: 2992 | 7 没看懂，不过在你的提示下，我对算法作了些修改：
就是看在比较的时候看比较的部分是否overlap, 不断地比较p1至p2之间的子串，比如：
case 1: 没有到p2就比较出大小了：
CxxxCxxCxxY <- begins with p1
CxxxCxxCxxZ <- begins with p2
case 2: 有overlap，这时候以p1至p2之间的子串为period, 比如下面的CxxxCxxCxxyy
，最大suffix p1要么保持不变，要么是最后一个y_i：
CxxxCxxCxxyy_____x1_____ _____y1_____ _____y2_____ _____y3_____
CxxxCxxCxxyy _____y1_____ _____y2_____ _____y3_____
|y_i|=|CxxxCxxCxxyy|=12
y_i与pattern CxxxCxxCxxyy比较，如果y_i
i.e. ：CxxxCxxCxxyy_____x1__________y1_____ _____y2_____ _____y3_____
如果y_i==CxxxCxxCxxyy，就继续比较 y_(i+1)
如果y_i>CxxxCxxCxxyy，那么最大suffix就是最后一个：_____yi_____
比如CaCaCb
CaCaCb
CaCb
period就是Ca,Cb>Ca，所以最大suffix就是最后一个Cb,
DbDbDa
DbDa
period就是Db, Da
【在 C***U 的大作中提到】
: 恩。我想了一个O(n)的，但是比你的复杂很多，空间也是O(n)的。关键是我觉得如果面
: 试的时候，现场不好写。你帮我看下对不对。
: 1） 找到字符串里面所有最大字母的位置，并且全部记录下来。
: 2） 然后看这些最大字符的后一位，还是找到最大的，并且把这些第二位也最大的记录
: 下来，然后给他们标记0，假设有k个标记0。把所有剩下的都标记为k，并且还记录这些
: 剩下的已经比较到哪个位置。这里第二位只过了2边。
: 3） 继续第二步，一直到找到一个唯一的最大字符串，或者有两个或以上的字符串遇到
: 下一个最大字符，那么就调用第二步记录的信息，看后一个最大字符串排名第几，如果
: 有一个唯一的排名最低，那么那个就是第一。如果不是唯一的，那么从第二步那里记录
: 的地方开始比较。
|
C***U
发帖数: 2406 | 8 我觉得你可能还是考虑的简单了
漏掉了一些情况
大s
【在 f*****e 的大作中提到】
: 没看懂，不过在你的提示下，我对算法作了些修改：
: 就是看在比较的时候看比较的部分是否overlap, 不断地比较p1至p2之间的子串，比如：
: case 1: 没有到p2就比较出大小了：
: CxxxCxxCxxY <- begins with p1
: CxxxCxxCxxZ <- begins with p2
: case 2: 有overlap，这时候以p1至p2之间的子串为period, 比如下面的CxxxCxxCxxyy
: ，最大suffix p1要么保持不变，要么是最后一个y_i：
: CxxxCxxCxxyy_____x1_____ _____y1_____ _____y2_____ _____y3_____
: CxxxCxxCxxyy _____y1_____ _____y2_____ _____y3_____
: |y_i|=|CxxxCxxCxxyy|=12
|
f*****e
发帖数: 2992 | 9 其实可以证明的，不过太过烦琐。而且我也考虑了p1与p2之间出现多次最大字符的情况。
【在 C***U 的大作中提到】
: 我觉得你可能还是考虑的简单了
: 漏掉了一些情况
:
: 大s
|
C***U
发帖数: 2406 | 10 我的方法肯定不好。。。
因为我觉得面试根本不可能写出来
所以不知道版上有没有大牛有简单方法
况。
【在 f*****e 的大作中提到】
: 其实可以证明的，不过太过烦琐。而且我也考虑了p1与p2之间出现多次最大字符的情况。
|
