g****s
发帖数: 16 | 1 常规问题后，问了个code的问题：
给一个substr，如何判断它在不在给定的str里面。
substr有两个新的符号可能在里面：
（1）* : 0-n个任意字符
（2）? ： 1个任意字符
太紧张了，所以面试者简化了题目，说去掉“？”，然后让code和测试：基本框架出来
了，但是好多特殊情况没有处理到，比如substr以“？”起头。
后来又问如果加入“*”有没有思路，刚说了两句就out of time了。
唉，失败了，不知道有没有下文。 |
h****8
发帖数: 599 | |
z*******y
发帖数: 578 | 3 string matching in a phone interview?
It''s difficult to finish this in such a short time, let alone writing code
for that. |
a**********s
发帖数: 588 | 4 I would construct a finite state machine to solve this kind of problem... |
z********y
发帖数: 109 | 5 using "*" and "?" as tokens to split the substr
iterate all indies of the first part, then using recursive if the next token
is "*"
it seems like the DFS scheme
【在 g****s 的大作中提到】
: 常规问题后，问了个code的问题：
: 给一个substr，如何判断它在不在给定的str里面。
: substr有两个新的符号可能在里面：
: （1）* : 0-n个任意字符
: （2）? ： 1个任意字符
: 太紧张了，所以面试者简化了题目，说去掉“？”，然后让code和测试：基本框架出来
: 了，但是好多特殊情况没有处理到，比如substr以“？”起头。
: 后来又问如果加入“*”有没有思路，刚说了两句就out of time了。
: 唉，失败了，不知道有没有下文。
|
g*******y
发帖数: 1930 | 6 好像可以把substr再按照*的位置，划分为若干subsubstr,然后用KMP一个一个找出现的位置，假设subsubstr是abc,d?ef,...，用KMP在string中找到第一个abc出现的位置，然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做，速度慢些。
对于?的处理，可以这样处理吧,在比较str和subsubstr的时候，自定义个bool
equalChar(char c1,char c2){ return c1==c2 || c2=='?'}来代替普通的c1 == c2判定。
PS,请问一下lz是怎么拿到ms电面的呢，internal refer，career fair，还是裸投简历？ 谢谢。 |
g*******y
发帖数: 1930 | 7 用? 来split不是很好吧。?在kmp预处理的时候，就当作是'?'本身，在比较str和
substr的时候，做为一个通配符。
另外，貌似题目只是问 是否存在match，不是找所有match，不需要DFS。如果找所有match，可以用DP的方法，类似于今年code jam qualification的最后一题。
token
【在 z********y 的大作中提到】
: using "*" and "?" as tokens to split the substr
: iterate all indies of the first part, then using recursive if the next token
: is "*"
: it seems like the DFS scheme
|
z********y
发帖数: 109 | 8 只有在"*"时使用recursive;"?"直接查下一个就行了。
the worst case needs to traverse all nodes in the DFS. Somehow, it is not
necessary for general cases.
match，可以用DP的方法，类似于今年code jam qualification的最后一题。
【在 g*******y 的大作中提到】
: 用? 来split不是很好吧。?在kmp预处理的时候，就当作是'?'本身，在比较str和
: substr的时候，做为一个通配符。
: 另外，貌似题目只是问 是否存在match，不是找所有match，不需要DFS。如果找所有match，可以用DP的方法，类似于今年code jam qualification的最后一题。
:
: token
|
M*****a
发帖数: 2054 | 9 简单的词法解析啊
这个自动状态机没多大啊
【在 g****s 的大作中提到】
: 常规问题后，问了个code的问题：
: 给一个substr，如何判断它在不在给定的str里面。
: substr有两个新的符号可能在里面：
: （1）* : 0-n个任意字符
: （2）? ： 1个任意字符
: 太紧张了，所以面试者简化了题目，说去掉“？”，然后让code和测试：基本框架出来
: 了，但是好多特殊情况没有处理到，比如substr以“？”起头。
: 后来又问如果加入“*”有没有思路，刚说了两句就out of time了。
: 唉，失败了，不知道有没有下文。
|
g*******y
发帖数: 1930 | 10 递归方法没错，不过我就是没有理解你说DFS的意思。你说的DFS，应该是针对推广后的
找所有match的问题吧？如果是的话，DFS貌似有重复计算，用dynamic programming比
较好。
【在 z********y 的大作中提到】
: 只有在"*"时使用recursive;"?"直接查下一个就行了。
: the worst case needs to traverse all nodes in the DFS. Somehow, it is not
: necessary for general cases.
:
: match，可以用DP的方法，类似于今年code jam qualification的最后一题。
|
|
|
z********y
发帖数: 109 | 11 每一个token的所有match都是一个node,每一个token到下一个token相当于一条有向的
connected path连接两个node,如果有n个"*"，相当于要找一条路径深度为n。找到了，
就结束；一直没有的话，也必须通过DFS遍历所有的node。好像没有重复。
如果找所有的匹配，就是要找所有的深度为n的路径。
【在 g*******y 的大作中提到】
: 递归方法没错，不过我就是没有理解你说DFS的意思。你说的DFS，应该是针对推广后的
: 找所有match的问题吧？如果是的话，DFS貌似有重复计算，用dynamic programming比
: 较好。
|
M*****a
发帖数: 2054 | 12 用一个状态表即可，没多少东西
后的
programming比
【在 z********y 的大作中提到】
: 每一个token的所有match都是一个node,每一个token到下一个token相当于一条有向的
: connected path连接两个node,如果有n个"*"，相当于要找一条路径深度为n。找到了，
: 就结束；一直没有的话，也必须通过DFS遍历所有的node。好像没有重复。
: 如果找所有的匹配，就是要找所有的深度为n的路径。
|
b***e
发帖数: 1419 | 13 kmp construstion also needs to take ? as wild-card, otherwise your kmp table
is wrong.
match，可以用DP的方法，类似于今年code jam qualification的最后一题。
【在 g*******y 的大作中提到】
: 用? 来split不是很好吧。?在kmp预处理的时候，就当作是'?'本身，在比较str和
: substr的时候，做为一个通配符。
: 另外，貌似题目只是问 是否存在match，不是找所有match，不需要DFS。如果找所有match，可以用DP的方法，类似于今年code jam qualification的最后一题。
:
: token
|
g*******y
发帖数: 1930 | 14 I just see that either way is wrong...
table
【在 b***e 的大作中提到】
: kmp construstion also needs to take ? as wild-card, otherwise your kmp table
: is wrong.
:
: match，可以用DP的方法，类似于今年code jam qualification的最后一题。
|
r****o
发帖数: 1950 | 15 谁能给个比较好的针对通配符的子字符串解法？
【在 g*******y 的大作中提到】
: I just see that either way is wrong...
:
: table
|
b***e
发帖数: 1419 | 16 Why?
【在 g*******y 的大作中提到】
: I just see that either way is wrong...
:
: table
|
g*******y
发帖数: 1930 | 17 if ? is treated as a normal char when compute KMP table,consider:
str: ababcd....
substr:ab?d
if ? is treated as a Wildcard when compute KMP table, consider:
str: abebcd....
substr:ab?d
【在 b***e 的大作中提到】
: Why?
|
b***e
发帖数: 1419 | 18 The first case is obviously out of question, as indicated in my original
post.
The second case is nothing wrong. The kmp table would be:
a b ? d
0 -1 0 0
which result in no match in
abebcd
【在 g*******y 的大作中提到】
: if ? is treated as a normal char when compute KMP table,consider:
: str: ababcd....
: substr:ab?d
: if ? is treated as a Wildcard when compute KMP table, consider:
: str: abebcd....
: substr:ab?d
|
g****s
发帖数: 16 | 19 校内的career fair。
的位置，假设subsubstr是abc,d?ef,...，用KMP在string中找到第一个abc出现的位置
，然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做，速度慢些。
判定。
历？ 谢谢。
【在 g*******y 的大作中提到】
: 好像可以把substr再按照*的位置，划分为若干subsubstr,然后用KMP一个一个找出现的位置，假设subsubstr是abc,d?ef,...，用KMP在string中找到第一个abc出现的位置，然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做，速度慢些。
: 对于?的处理，可以这样处理吧,在比较str和subsubstr的时候，自定义个bool
: equalChar(char c1,char c2){ return c1==c2 || c2=='?'}来代替普通的c1 == c2判定。
: PS,请问一下lz是怎么拿到ms电面的呢，internal refer，career fair，还是裸投简历？ 谢谢。
|
p*********a
发帖数: 21 | 20 Maybe KMP is enough! I wrote a program, let me know if there's any bug in it.
#include
#include
#include
#include
using namespace std;
string src, p;
vector v;
vector > next;
void KMP_init(int ix) {
next[ix].resize(v[ix].size());
next[ix][0] = -1;
int i, j;
i = 0; j = -1;
while(i
if(j==-1||v[ix][i]==v[ix][j]||v[ix][i]=='?') {
i++; j++;
if(v[ix][i]==v[ix][j]||v[ix][i]=='?')
next[ix][i] = next[ix][j];
else
next[ix][i] = j |
|
|
g****s
发帖数: 16 | 21 这个代码要在20分钟的电面里面写出来，牛啊！我惭愧～ |
r**u
发帖数: 1567 | 22 这题只要求，给一个substr，如何判断它在不在给定的str里面。substr has ?/*.
不用那么复杂吧，遇到*就skip就可以了，遇到? match下一个。不是?/*就在str里找第
一个substr[next]。
【在 g****s 的大作中提到】
: 常规问题后，问了个code的问题：
: 给一个substr，如何判断它在不在给定的str里面。
: substr有两个新的符号可能在里面：
: （1）* : 0-n个任意字符
: （2）? ： 1个任意字符
: 太紧张了，所以面试者简化了题目，说去掉“？”，然后让code和测试：基本框架出来
: 了，但是好多特殊情况没有处理到，比如substr以“？”起头。
: 后来又问如果加入“*”有没有思路，刚说了两句就out of time了。
: 唉，失败了，不知道有没有下文。
|
h*********e
发帖数: 56 | 23 我在网上看见一个巧妙的解法，不过是指数时间。写 linear time matching 代码对于
面试太难了点。
bool match(const char *pattern, const char *string)
{
switch (*pattern)
{
case '\0': return !*string;
case '*': return match(pattern+1, string) ||
(*string && match(pattern, string+1));
case '?': return *string && match(pattern+1, string+1);
default : return (*pattern == *string) &&
match(pattern+1, string+1);
}
} |
g*****u
发帖数: 298 | 24 如果只找一个match为什么要DFS?
string: abcabcabac
pattern: ab*ab*ac
string在第三个ab的时候mismatch,但是你不需要回溯到前面两个ab的pattern的。就是
说前面两个ab的match不需要再考虑更改了。
【在 z********y 的大作中提到】
: 每一个token的所有match都是一个node,每一个token到下一个token相当于一条有向的
: connected path连接两个node,如果有n个"*"，相当于要找一条路径深度为n。找到了，
: 就结束；一直没有的话，也必须通过DFS遍历所有的node。好像没有重复。
: 如果找所有的匹配，就是要找所有的深度为n的路径。
|
j***r
发帖数: 69 | 25 我提供一个思路：
先把这个问题简化为---判断substr是否是str的一个suffix. 这个可以用 Dynamic
Programming 在 O(mn)的时间完成。剩下的就容易了。 |
c******f
发帖数: 2144 | |
h*******x
发帖数: 12808 | 27 这个问题挺难啊。
【在 g****s 的大作中提到】
: 常规问题后，问了个code的问题：
: 给一个substr，如何判断它在不在给定的str里面。
: substr有两个新的符号可能在里面：
: （1）* : 0-n个任意字符
: （2）? ： 1个任意字符
: 太紧张了，所以面试者简化了题目，说去掉“？”，然后让code和测试：基本框架出来
: 了，但是好多特殊情况没有处理到，比如substr以“？”起头。
: 后来又问如果加入“*”有没有思路，刚说了两句就out of time了。
: 唉，失败了，不知道有没有下文。
|
w******1
发帖数: 520 | |
