愚蠢的人类，我还会再回来的……哈哈哈哈……【上升飘走……】 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

愚蠢的人类，我还会再回来的……哈哈哈哈……【上升飘走……】

愚蠢的人类，我还会再回来的……哈哈哈哈……【上升飘走……】# Joke - 肚皮舞运动

h*82012-04-27 07:04

1 楼

The basic idea is fill in a table for a matching path. If the last pair
matches, the whole string will match.
match[i][j] is the array (to match string[i] with pattern[j]), which is of (
string length + 1)*(pattern length + 1).
match[0][*] and match[*][0] is padded with false.
Then the function is something like:
match[i][j] =
1. if pattern char='.', match[i][j]=match[i-1][j-1]
2. if pattern char='*', match[i][j]=match[i][j-1] //match 0 character
||match[i-1][j] //match any character
3. if pattern char=string char, match[i][j]=match[i-1][j-1]
4. otherwise, not matched.
大家看看对不对？

w*s2012-04-27 07:04

2 楼

@楚惜刀: 蹦蹦床！欧也！
@潘海天: 愚蠢的人类，我还会再回来的……哈哈哈哈……【上升飘走……】
@fall_ark:233，科罗拉多大学波德分校校园里不知怎么晃荡进了一只熊，最后出动了
警方打麻醉才把它搞定……但是这张抓拍是怎么回事啊喂！虽然大概能想到当时的状况
但能够捕捉到这个瞬间也太喜感了吧混蛋！ (╯°□°）╯ （图自科罗拉多大学独立
报，摄影者Andy Duann）

g*t2012-04-27 07:04

3 楼

不对。
match[*][0]要初始化为true，因为任何字符串都匹配空模式。这是用来“起头”用的。
match[0][1:n]要初始化为false，因为空字符串不匹配任何非空模式。这用来保证匹配
是完整的。
其他的条件没来的及看。

L*n2012-04-27 07:04

4 楼

爬到树上了，然后被一枪放倒？

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

: @楚惜刀: 蹦蹦床！欧也！
: @潘海天: 愚蠢的人类，我还会再回来的……哈哈哈哈……【上升飘走……】
: @fall_ark:233，科罗拉多大学波德分校校园里不知怎么晃荡进了一只熊，最后出动了
: 警方打麻醉才把它搞定……但是这张抓拍是怎么回事啊喂！虽然大概能想到当时的状况
: 但能够捕捉到这个瞬间也太喜感了吧混蛋！ (╯°□°）╯ （图自科罗拉多大学独立
: 报，摄影者Andy Duann）

h*82012-04-27 07:04

5 楼

我的意思是好像可以用DP做，为啥大家都用recursion?

的。

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

: 不对。
: match[*][0]要初始化为true，因为任何字符串都匹配空模式。这是用来“起头”用的。
: match[0][1:n]要初始化为false，因为空字符串不匹配任何非空模式。这用来保证匹配
: 是完整的。
: 其他的条件没来的及看。

n*w2012-04-27 07:04

6 楼

如果像这么定义 .和* 可以用DP。
很多定义是不能DP的，比如
*表示匹配前一个字符任意次
+表示匹配前一个字符至少一次
a-z表示匹配a-z之间任意字符
。。。
有一些不能DP的正则式定义，因为DP的前提是make a choice之后的子问题跟choice本
身没有dependency。
另外正则式搞复杂了，面试不一定有时间用DP写白板。一个面试session 45分钟，一般
3道coding，至少也得2道。时间还是紧张了。当然牛人除外。

(

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

: The basic idea is fill in a table for a matching path. If the last pair
: matches, the whole string will match.
: match[i][j] is the array (to match string[i] with pattern[j]), which is of (
: string length + 1)*(pattern length + 1).
: match[0][*] and match[*][0] is padded with false.
: Then the function is something like:
: match[i][j] =
: 1. if pattern char='.', match[i][j]=match[i-1][j-1]
: 2. if pattern char='*', match[i][j]=match[i][j-1] //match 0 character
: ||match[i-1][j] //match any character

j*22012-04-27 07:04

7 楼

没错。DP只能用来解wildcard,不能解 regex.即使是wildcard,也比递归要难写（反正
我肯定当场白板写不出来）。

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

: 如果像这么定义 .和* 可以用DP。
: 很多定义是不能DP的，比如
: *表示匹配前一个字符任意次
: +表示匹配前一个字符至少一次
: a-z表示匹配a-z之间任意字符
: 。。。
: 有一些不能DP的正则式定义，因为DP的前提是make a choice之后的子问题跟choice本
: 身没有dependency。
: 另外正则式搞复杂了，面试不一定有时间用DP写白板。一个面试session 45分钟，一般
: 3道coding，至少也得2道。时间还是紧张了。当然牛人除外。

h*82012-04-27 07:04

8 楼

这个不对吧。* in regex can also be done in the following way
if *(pat+1) == ‘*’, regex_match(str, pat) =
• regex_match(str, pat+2) OR // match 0 occurrence – “ab”, “a*
ab”
• regex_match(str+1, pat) if equal_char(*str, *pat) // match 1
occurrence – “aab”, “a*b”
And the above can be achieved with DP:
match[i][j] is the array (to match string[i] with pattern[j]), which is of (
string length + 1)*(pattern length + 1).
Initialize:
match[0][0] = true
match[*][0] = false if str is not empty
match[0][*] = pattern is “a*b*.*”? true:false
Then the function is something like:
match[i][j] =
1. if pattern char='.', match[i][j]=match[i-1][j-1]
2. if pattern char='*', match[i][j]=match[i][j-2] //match 0 character –
to pass “a*”
|| match[i-1][j] if str[i] = pat[j-1] // match 1 occurrence – “aab”, “a*
b”
3. if pattern char=string char, match[i][j]=match[i-1][j-1]
4. otherwise, not matched.

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