B*******1
发帖数: 2454 | 1 求一个字符中连续出现次数最多的子串
abcbcbcabc 中，连续出现的字符串为bc,连续三次
abcccabc中，最多的为c
要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
谢谢。 |
l******c
发帖数: 2555 | 2 suffix tree
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
|
q****x
发帖数: 7404 | 3 不连续的我也不会。谁给讲讲？
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
|
a**********2
发帖数: 340 | 4 建suffix tree，节点上计数
【在 q****x 的大作中提到】
: 不连续的我也不会。谁给讲讲？
|
q****x
发帖数: 7404 | 5 给个例子？
【在 a**********2 的大作中提到】
: 建suffix tree，节点上计数
|
a**********2
发帖数: 340 | 6 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
后找出最大计数路径。
其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
的出现频率
连续的话用就不知道怎么弄了 |
q****x
发帖数: 7404 | 7 abcd, bc不是前缀也不是后缀啊？
【在 a**********2 的大作中提到】
: 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
: 后找出最大计数路径。
: 其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
: 的出现频率
: 连续的话用就不知道怎么弄了
|
b******g
发帖数: 1721 | 8 这个suffix tree本身就是连续substring啊。
你的意思是不是“如果不是连续的就不知道怎么弄了”？
【在 a**********2 的大作中提到】
: 画一颗后缀树，建立过程中存在的节点就将这个节点加一，不存在就创建并设为1，最
: 后找出最大计数路径。
: 其实很好理解，后缀树是字符串所有后缀的字串的集合而成的，计数就相当于统计字串
: 的出现频率
: 连续的话用就不知道怎么弄了
|
b******g
发帖数: 1721 | 9 bcd 是后缀，而且在suffix tree里面，bc是从root出发的substring。可以bottom up
计数，正如airplane1022所描述的。
【在 q****x 的大作中提到】
: abcd, bc不是前缀也不是后缀啊？
|
m**q
发帖数: 189 | 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很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
|
B*******1
发帖数: 2454 | 11 其实这个我也想过，但是这样子似乎复杂度很高啊，sort后找完common prefix再找等
差数列。
【在 m**q 的大作中提到】
: 我觉得连续的子串也可以用suffix array啊
: 比如 abcbcbcabc
: 0123456789
: 0 abc
: 9 abcbcbcbcabc
: 5 bcabc
: 3 bcbcabc
: 1 bcbcbcabc
: 9 c
: 6 cabc
|
a********m
发帖数: 15480 | 12 长度有关系么？没限制的话找出现次数最多的字符就可以了吧？
【在 B*******1 的大作中提到】
: 求一个字符中连续出现次数最多的子串
: abcbcbcabc 中，连续出现的字符串为bc,连续三次
: abcccabc中，最多的为c
: 要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
: 谢谢。
|
