（= 中秋快乐 =） - 未名空间MITBBS历史存档

H*M2012-09-29 07:09

1 楼

s1: abcdefg
s2: dcbe
要你找到一个s1中的一个substring,matches s2,但是，这个substring的顺序不重要，
比如bcde also matches dcbe
KMP,和surfix tree都不可以了。
有没有什么efficient的方法？
大家讨论讨论。好象在哪看过这题。

y*52012-09-29 07:09

2 楼

祝福~ 月圆人圆~~~~~~
想了就回来看看大家，呵呵，地球这边感觉很好，山上可以看海，海的那边是岸，这边
也是岸，觉得是岸，就靠岸了，有点唯心，灯火阑珊很温暖。不曾想过，连根拔起之后
，会有今天这份踏实，嗯。
多多保重啦！

a*h2012-09-29 07:09

3 楼

Simple-minded (m+n)log(m) 够好不？ m = |s1|, n = |s2|。直接在 s1 上搞个BST啥
的。

【在 H*M 的大作中提到】

: s1: abcdefg
: s2: dcbe
: 要你找到一个s1中的一个substring,matches s2,但是，这个substring的顺序不重要，
: 比如bcde also matches dcbe
: KMP,和surfix tree都不可以了。
: 有没有什么efficient的方法？
: 大家讨论讨论。好象在哪看过这题。

b*k2012-09-29 07:09

4 楼

心安处，便是家，这种感觉真好：）

【在 y******5 的大作中提到】

: 祝福~ 月圆人圆~~~~~~
: 想了就回来看看大家，呵呵，地球这边感觉很好，山上可以看海，海的那边是岸，这边
: 也是岸，觉得是岸，就靠岸了，有点唯心，灯火阑珊很温暖。不曾想过，连根拔起之后
: ，会有今天这份踏实，嗯。
: 多多保重啦！

w*p2012-09-29 07:09

5 楼

substring 得字母在s1中是连续的吗？
s1: abcdef
s2: bed
结果是 bde 还是 failed.

【在 H*M 的大作中提到】

: s1: abcdefg
: s2: dcbe
: 要你找到一个s1中的一个substring,matches s2,但是，这个substring的顺序不重要，
: 比如bcde also matches dcbe
: KMP,和surfix tree都不可以了。
: 有没有什么efficient的方法？
: 大家讨论讨论。好象在哪看过这题。

y*52012-09-29 07:09

6 楼

是呀，很难得
抱抱~~~~ ：）

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

: 心安处，便是家，这种感觉真好：）

H*M2012-09-29 07:09

7 楼

failed.
必须连续
你上次面试怎么样?

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

: substring 得字母在s1中是连续的吗？
: s1: abcdef
: s2: bed
: 结果是 bde 还是 failed.

l*r2012-09-29 07:09

8 楼

赞美
祝福~

【在 y******5 的大作中提到】

: 祝福~ 月圆人圆~~~~~~
: 想了就回来看看大家，呵呵，地球这边感觉很好，山上可以看海，海的那边是岸，这边
: 也是岸，觉得是岸，就靠岸了，有点唯心，灯火阑珊很温暖。不曾想过，连根拔起之后
: ，会有今天这份踏实，嗯。
: 多多保重啦！

b*e2012-09-29 07:09

9 楼

没必要. 给s2建个按字母表的hash, 扫一遍s1就行了.

【在 a*******h 的大作中提到】

: Simple-minded (m+n)log(m) 够好不？ m = |s1|, n = |s2|。直接在 s1 上搞个BST啥
: 的。

L*t2012-09-29 07:09

10 楼

祝福
摸摸圆圆的悠悠

【在 y******5 的大作中提到】

: 祝福~ 月圆人圆~~~~~~
: 想了就回来看看大家，呵呵，地球这边感觉很好，山上可以看海，海的那边是岸，这边
: 也是岸，觉得是岸，就靠岸了，有点唯心，灯火阑珊很温暖。不曾想过，连根拔起之后
: ，会有今天这份踏实，嗯。
: 多多保重啦！

H*M2012-09-29 07:09

11 楼

这个不work吧.是substring,不是sub sequence

【在 b***e 的大作中提到】

: 没必要. 给s2建个按字母表的hash, 扫一遍s1就行了.

j*j2012-09-29 07:09

12 楼

sweet

【在 y******5 的大作中提到】

: 祝福~ 月圆人圆~~~~~~
: 想了就回来看看大家，呵呵，地球这边感觉很好，山上可以看海，海的那边是岸，这边
: 也是岸，觉得是岸，就靠岸了，有点唯心，灯火阑珊很温暖。不曾想过，连根拔起之后
: ，会有今天这份踏实，嗯。
: 多多保重啦！

w*p2012-09-29 07:09

13 楼

我本来也是这样想的。但如果substring 得字母在s1中要连续的，要加最后一步
在s1中如果被hash的字母不连续， failed.
1. 看所有s2字母和s1中的字母是否有1对1的关系。有的话，mark s2的字母（hash)
2. 看被 mark 的s1 字母是否连续
不过如果s1,s2 的string有字母重复好像不可以了

【在 b***e 的大作中提到】

: 没必要. 给s2建个按字母表的hash, 扫一遍s1就行了.

wh2012-09-29 07:09

14 楼

看来是回啦，羡慕踏实，哈哈。

【在 y******5 的大作中提到】

: 祝福~ 月圆人圆~~~~~~
: 想了就回来看看大家，呵呵，地球这边感觉很好，山上可以看海，海的那边是岸，这边
: 也是岸，觉得是岸，就靠岸了，有点唯心，灯火阑珊很温暖。不曾想过，连根拔起之后
: ，会有今天这份踏实，嗯。
: 多多保重啦！

w*p2012-09-29 07:09

15 楼

look at your answer.....not good sign
If I have good news, you will know

【在 H*M 的大作中提到】

: failed.
: 必须连续
: 你上次面试怎么样?

y*52012-09-29 07:09

16 楼

谢谢牛筋~ 也祝福你有吃有喝有的玩有水灌~

【在 l*r 的大作中提到】

: 赞美
: 祝福~

H*M2012-09-29 07:09

17 楼

I am really sorry...根本没往那方面想.只是copy你post里的.
I am sensitive to those bad words too...

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

: look at your answer.....not good sign
: If I have good news, you will know

y*52012-09-29 07:09

18 楼

祝福打印机 + 打手，让你乱摸 >_<

【在 L******t 的大作中提到】

: 祝福
: 摸摸圆圆的悠悠

b*e2012-09-29 07:09

19 楼

有重复也没关系. 两个hash, 一个存s2的inverted index, 一个存现在已经找到的. 设
两个指针i, j来traverse s1(j >= i), 多退(i++)少补(j++), 没找到就重新来过. 唯一
tricky的地方就是如果j++多扫进来一个字母, 假设是a, 那么i++要一直repeat直到把上一个a吐出
来. 沿路经过都要吐出去.

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

: 我本来也是这样想的。但如果substring 得字母在s1中要连续的，要加最后一步
: 在s1中如果被hash的字母不连续， failed.
: 1. 看所有s2字母和s1中的字母是否有1对1的关系。有的话，mark s2的字母（hash)
: 2. 看被 mark 的s1 字母是否连续
: 不过如果s1,s2 的string有字母重复好像不可以了

y*52012-09-29 07:09

20 楼

bless~

【在 j***j 的大作中提到】

: sweet

H*M2012-09-29 07:09

21 楼

对阿.按你说的
s1: aeeeefg
s2: dcbe
就 return true了.
如果s1中没有s2的组成字母的dup就可以了,看有没有连续的4个

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

: 我本来也是这样想的。但如果substring 得字母在s1中要连续的，要加最后一步
: 在s1中如果被hash的字母不连续， failed.
: 1. 看所有s2字母和s1中的字母是否有1对1的关系。有的话，mark s2的字母（hash)
: 2. 看被 mark 的s1 字母是否连续
: 不过如果s1,s2 的string有字母重复好像不可以了

y*52012-09-29 07:09

22 楼

在哪里踏实都好~ 每个人的磁场不一样，嘻嘻

【在 wh 的大作中提到】

: 看来是回啦，羡慕踏实，哈哈。

H*M2012-09-29 07:09

23 楼

没看懂...

唯一
把上一个a吐出

【在 b***e 的大作中提到】

: 有重复也没关系. 两个hash, 一个存s2的inverted index, 一个存现在已经找到的. 设
: 两个指针i, j来traverse s1(j >= i), 多退(i++)少补(j++), 没找到就重新来过. 唯一
: tricky的地方就是如果j++多扫进来一个字母, 假设是a, 那么i++要一直repeat直到把上一个a吐出
: 来. 沿路经过都要吐出去.

L*t2012-09-29 07:09

24 楼

。。。
快写个归海小白鼠的故事吧。

【在 y******5 的大作中提到】

: 祝福打印机 + 打手，让你乱摸 >_<

b*e2012-09-29 07:09

25 楼

#include "stdio.h"
#include "string.h"
int c2i(char c) {
return c - 'a';
}
int i2c(int i) {
return i + 'a';
}
int* invertedIndex(char* s) {
int len = strlen(s);
int* hash = new int[26];
for (int i = 0; i < 26; i++) {
hash[i] = 0;
}
for (int i = 0; i < len; i++) {
int c = s[i];
hash[c2i(c)] += 1;
}
return hash;
}
void printHash(int* a) {
for (int i = 0; i < 26; i++) {
printf("%i, ", a[i]);
}
}
int patternMatch(char* s1, c

w*p2012-09-29 07:09

26 楼

还没仔细看程序，先赞一下热情。