问个算法题# JobHunting - 待字闺中
B*1
1 楼
求一个字符中连续出现次数最多的子串
abcbcbcabc 中，连续出现的字符串为bc,连续三次
abcccabc中，最多的为c
要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
谢谢。
abcbcbcabc 中，连续出现的字符串为bc,连续三次
abcccabc中，最多的为c
要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
谢谢。
l*c
2 楼
suffix tree
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
q*x
3 楼
不连续的我也不会。谁给讲讲？
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
a*2
4 楼
建suffix tree，节点上计数
【在 q****x 的大作中提到】
: 不连续的我也不会。谁给讲讲？
【在 q****x 的大作中提到】
: 不连续的我也不会。谁给讲讲？
q*x
5 楼
给个例子？
【在 a**********2 的大作中提到】
: 建suffix tree，节点上计数
【在 a**********2 的大作中提到】
: 建suffix tree，节点上计数
a*2
6 楼
画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
后找出最大计数路径。
其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
的出现频率
连续的话用就不知道怎么弄了
后找出最大计数路径。
其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
的出现频率
连续的话用就不知道怎么弄了
q*x
7 楼
abcd, bc不是前缀也不是后缀啊？
【在 a**********2 的大作中提到】
: 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
: 后找出最大计数路径。
: 其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
: 的出现频率
: 连续的话用就不知道怎么弄了
【在 a**********2 的大作中提到】
: 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
: 后找出最大计数路径。
: 其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
: 的出现频率
: 连续的话用就不知道怎么弄了
b*g
8 楼
这个suffix tree本身就是连续substring啊。
你的意思是不是“如果不是连续的就不知道怎么弄了”？
【在 a**********2 的大作中提到】
: 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
: 后找出最大计数路径。
: 其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
: 的出现频率
: 连续的话用就不知道怎么弄了
你的意思是不是“如果不是连续的就不知道怎么弄了”？
【在 a**********2 的大作中提到】
: 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
: 后找出最大计数路径。
: 其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
: 的出现频率
: 连续的话用就不知道怎么弄了
b*g
9 楼
bcd 是后缀，而且在suffix tree里面，bc是从root出发的substring。可以bottom up
计数，正如airplane1022所描述的。
【在 q****x 的大作中提到】
: abcd, bc不是前缀也不是后缀啊？
计数，正如airplane1022所描述的。
【在 q****x 的大作中提到】
: abcd, bc不是前缀也不是后缀啊？
m*q
10 楼
我觉得连续的子串也可以用suffix array啊
比如 abcbcbcabc
0123456789
0 abc
9 abcbcbcbcabc
5 bcabc
3 bcbcabc
1 bcbcbcabc
9 c
6 cabc
4 cbcabc
2 cbcbcabc
把sort后的array扫一遍，对于相邻的两个子串，判断它们的最长公共前缀
的长度是否是个等差数列，且这个等差数列的差等于相邻的两个子串的
index之差
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
比如 abcbcbcabc
0123456789
0 abc
9 abcbcbcbcabc
5 bcabc
3 bcbcabc
1 bcbcbcabc
9 c
6 cabc
4 cbcabc
2 cbcbcabc
把sort后的array扫一遍，对于相邻的两个子串，判断它们的最长公共前缀
的长度是否是个等差数列，且这个等差数列的差等于相邻的两个子串的
index之差
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
B*1
11 楼
其实这个我也想过，但是这样子似乎复杂度很高啊，sort后找完common prefix再找等
差数列。
【在 m**q 的大作中提到】
: 我觉得连续的子串也可以用suffix array啊
: 比如 abcbcbcabc
: 0123456789
: 0 abc
: 9 abcbcbcbcabc
: 5 bcabc
: 3 bcbcabc
: 1 bcbcbcabc
: 9 c
: 6 cabc
差数列。
【在 m**q 的大作中提到】
: 我觉得连续的子串也可以用suffix array啊
: 比如 abcbcbcabc
: 0123456789
: 0 abc
: 9 abcbcbcbcabc
: 5 bcabc
: 3 bcbcabc
: 1 bcbcbcabc
: 9 c
: 6 cabc
a*m
12 楼
长度有关系么？没限制的话找出现次数最多的字符就可以了吧？
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
相关阅读
Yodle puzzle,作出可申请工作一个人的小公司可以支持 OPT 吗 ？C++ Q72: template (skillport)美国移民局长：外籍人士找工设限大公司的intern是不是也可以sponsor H1B啊？口头offer到正式offer要多久？薪水啥时候谈？Vanguard 是不是不要H1B？求人辅导PIVOT-TABLE报一个H1B找学校lab manager职位一些问题是在这儿发帖吗？twitter电面GRMI ( Global Resource Management Inc.) 如何？招 Business Intelligence Developer问题，请高手指教finally know that BB is bloomberg紧急求助，h1b-f2被拒，out of status了，怎么办？****求建议－－如何negotiate offer****怎么跟HR联系？询问工资简单说说生物小硕找工作的经历