大牛们，蓉2股神的1020这波还会来吗? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

大牛们，蓉2股神的1020这波还会来吗?

大牛们，蓉2股神的1020这波还会来吗?# Stock

w*k2010-06-11 07:06

1 楼

Given a string, find the substring which occurs most frequently. This
substring must have length between K and L, and must have no more than M
distinct characters, assuming string has only lower case letters 'a' to 'z'.
－－
解法很多，最优的是什么？
我的想法是类似于sliding window, 以每个字符为substring起点，考虑长为K的子串
，将其中字符hash set以知道distinct chars是不是在M以内，然后将子串放入hash
map以累计频率；然后长度K＋＋，放入新的字符更新hash set和map，当然只需要考虑
新字符带来的改变。起始位置＋＋时也一样，只需考虑扔掉字符带来的改变。
因为要求用C，我只好自己写hash set 和 map，还有 hash function，再加上的确对C
不熟，虽然C＋＋那是杠杠的，没写完，如果用C＋＋的话应该能完成，但不知道是不是
最优的。

p*d2010-06-11 07:06

2 楼

蓉2股神DT, 所以涨跌无所谓了

l*a2010-06-11 07:06

3 楼

这个基本可以看成是两道题
1)Given a string, find the substring which occurs most frequently.
This substring must have length between K and L
u should use rolling hash
2) sliding window.
u should use int[26] counter array and a variable to indicate unique
characters
count... if use hashSet,u can't remember how many time each char occurs
then how does it work for sliding window

'.
对C

【在 w****k 的大作中提到】

: Given a string, find the substring which occurs most frequently. This
: substring must have length between K and L, and must have no more than M
: distinct characters, assuming string has only lower case letters 'a' to 'z'.
: －－
: 解法很多，最优的是什么？
: 我的想法是类似于sliding window, 以每个字符为substring起点，考虑长为K的子串
: ，将其中字符hash set以知道distinct chars是不是在M以内，然后将子串放入hash
: map以累计频率；然后长度K＋＋，放入新的字符更新hash set和map，当然只需要考虑
: 新字符带来的改变。起始位置＋＋时也一样，只需考虑扔掉字符带来的改变。
: 因为要求用C，我只好自己写hash set 和 map，还有 hash function，再加上的确对C

T*s2010-06-11 07:06

4 楼

it looks you did not follow her post recently
R2 switched to the bright side yesterday

u*w2010-06-11 07:06

5 楼

感觉有点奇怪，如果长度在【K， L】，那么长度为K的子串（把L长度串的尾巴去掉）
一定更频繁，所以只要找长度为K的子串，一共有n - k + 1个子串，用hash记录他们的
次数，找出出现次数最多的，至于distinct character，用sliding windows的方法,
用【26】数组记录字符出现的情况。

b*u2010-06-11 07:06

6 楼

靠，R2的大嘴巴你还信阿

z*g2010-06-11 07:06

7 楼

Build a suffix trie: keep track of how many times a node has been visited
encountered during the construction process. We could track only the nodes
that are in between level K and L, and maintain a global maximum in the mean
while.
The word represented by the trie node associated with the global maximum is
the answer.
Time and space complexity are both O(n2).

p*d2010-06-11 07:06

8 楼

ElliottJr,铁杆蓉粉
发信人: ElliottJr (Froglet), 信区: Complain
标题: Re: [投诉]stock版版主ElliottJr乱封人
发信站: BBS 未名空间站 (Thu Jun 3 02:24:17 2010, 美东)
ronger12345的预测很多是带有假设条件的，无所谓对错，其他的有对有错，很正常，
所有预测的人都是有时对有时错。这两个帖没有举证，没有讨论的意图，是明显的挖苦
讽刺，这样的帖在stock是不允许的。

z*g2010-06-11 07:06

9 楼

#include
#include
#include
typedef struct trie {
int count;
const char *start;
int len;
struct trie *children[256];
} trie;
static inline trie *make_trie_node(const char *start, int len) {
trie *t, temp = {
.start = start,
.len = len
};
t = malloc(sizeof(trie));
memcpy(t, &temp, sizeof(trie));
memset(&t->children, 0, sizeof(t->children));
return t;
}
const char *most_frequent_substr(const char *str, int k, int l) {
int len, level, i, j;
int max_occur = 0;
trie *max_node = NULL, *root, *cursor;
char *ret;
len = strlen(str);
root = make_trie_node(NULL, 0);
for(i = 0; i < len; ++ i) {
cursor = root;
level = 0;
/* inserts each suffix into the trie */
for(j = i; j < len; ++ j) {
if(!cursor->children[(int)str[j]]) {
cursor->children[(int)str[j]] = make_trie_node(str + i, j -
i + 1);
}
cursor = cursor->children[(int)str[j]];
level += 1;
cursor->count += 1;
if(level >= k && level <= l) {
if(cursor->count > max_occur) {
max_occur = cursor->count;
max_node = cursor;
}
}
}
}
ret = malloc(max_node->len + 1);
memcpy(ret, max_node->start, len);
ret[max_node->len] = '\0';
/* tear down ommited */
return ret;
}

p*d2010-06-11 07:06

10 楼

大盘跌, 喊跌
大盘涨, 喊涨
一天一变，繁殖的厉害,
单边市的股神,
http://www.mitbbs.com/clubarticle_t/stockbash/31206873.html

【在 T*********s 的大作中提到】

: it looks you did not follow her post recently
: R2 switched to the bright side yesterday

m*g2010-06-11 07:06

11 楼

很牛的c code!!

【在 z******g 的大作中提到】

: #include
: #include
: #include
: typedef struct trie {
: int count;
: const char *start;
: int len;
: struct trie *children[256];
: } trie;
: static inline trie *make_trie_node(const char *start, int len) {

p*d2010-06-11 07:06

12 楼

蓉2股神删168喊错的帖子已经尽人皆知
卫星上天,股神落地

w*k2010-06-11 07:06

13 楼

我没仔细看代码，你的O是多少？Build trie 有O(N)的算法，但很复杂，O（N^2）的算
法恐怕不能通过测试，字符串记得有100k的长度。

【在 z******g 的大作中提到】

p*d2010-06-11 07:06

14 楼

蓉2股神身穿绿内裤，,,腰别红腰带,,，
胸前一个大大的B字，,,光芒四射,,,
时而显示为BULL，,,时而显示为BEAR，,, ...

z*g2010-06-11 07:06

15 楼

O(n2)的。
O(n)的我不会所以不知道行不行。

【在 w****k 的大作中提到】

: 我没仔细看代码，你的O是多少？Build trie 有O(N)的算法，但很复杂，O（N^2）的算
: 法恐怕不能通过测试，字符串记得有100k的长度。

a*82010-06-11 07:06

16 楼

楼主疯了，快被封了。

s*72010-06-11 07:06

17 楼

是爷们，就别和女人较劲，除了xxx的时候

【在 p*****d 的大作中提到】

: 蓉2股神DT, 所以涨跌无所谓了

g*u2010-06-11 07:06

18 楼

删贴，删贴咯。自己整改，把贴删了。
再bashing就要关小黑屋了!

n*c2010-06-11 07:06

19 楼

小声的问一声，不是说是N(北上)S(南下)吗？

【在 p*****d 的大作中提到】

: 蓉2股神身穿绿内裤，,,腰别红腰带,,，
: 胸前一个大大的B字，,,光芒四射,,,
: 时而显示为BULL，,,时而显示为BEAR，,, ...