g***j
发帖数: 1275 | 1 string s 和 string t，求 t 在s中出现的次数，不一定要是连续的
比如
ababc 和 ab 返回3
ababca 和 aa 返回 3
怎么高效的做这个？ |
a**********0
发帖数: 422 | 2 第二个例子没看懂 你的意思是S之中选取若干的一个permutation就是t 看有多少选择
方法？ |
t**r
发帖数: 3428 | |
l*********8
发帖数: 4642 | 4 dp
count[i][j] 表示S前i个字符里包含T的前j个字符的次数
【在 g***j 的大作中提到】
: string s 和 string t，求 t 在s中出现的次数，不一定要是连续的
: 比如
: ababc 和 ab 返回3
: ababca 和 aa 返回 3
: 怎么高效的做这个？
|
b***y
发帖数: 177 | 5 应该有O(n)的解法，就是mininum window string的思路
【在 g***j 的大作中提到】
: string s 和 string t，求 t 在s中出现的次数，不一定要是连续的
: 比如
: ababc 和 ab 返回3
: ababca 和 aa 返回 3
: 怎么高效的做这个？
|
t**r
发帖数: 3428 | |
l*********8
发帖数: 4642 | 7 请问是哪本？谢谢
【在 t**r 的大作中提到】
: 可以参照算法书 390页
|
a**********0
发帖数: 422 | 8 我觉得他不是这样的意思 比如他第二个例子 我不知道三是怎么弄出来的 如果是把第
一个a和最后一个a组成的也算aa 那就是三个 但是需要跳过第二个a
【在 l*********8 的大作中提到】
: dp
: count[i][j] 表示S前i个字符里包含T的前j个字符的次数
|
l*********8
发帖数: 4642 | 9 是要跳过第二个a
【在 a**********0 的大作中提到】
: 我觉得他不是这样的意思 比如他第二个例子 我不知道三是怎么弄出来的 如果是把第
: 一个a和最后一个a组成的也算aa 那就是三个 但是需要跳过第二个a
|
a**********0
发帖数: 422 | 10 这样就不能用dp了啊 int dp[i] 表示已经有的t中的字符数 如果跳过第二个a 那就有
两种状态 有可能是一 有可能是二
我觉得他就是从s中挑t.length()个字符的排列 看看有多少中挑法 可以和t一样
这个是典型的递归
【在 l*********8 的大作中提到】
: 是要跳过第二个a
|
l*********8
发帖数: 4642 | 11 S = "ababca", T="aa"这个例子
count[0][0], count[1][0]... count[5][0]的值是：
1 1 2 2 2 3
count[0][1], count[1][1]... count[5][1]的值是：
0 0 1 1 1 3
递推:(没写边界情况）
if (S[i] == T[j])
count[i][j] = count[i-1][j] + count[i-1][j-1];
else
count[i][j] = count[i-1][j];
【在 a**********0 的大作中提到】
: 这样就不能用dp了啊 int dp[i] 表示已经有的t中的字符数 如果跳过第二个a 那就有
: 两种状态 有可能是一 有可能是二
: 我觉得他就是从s中挑t.length()个字符的排列 看看有多少中挑法 可以和t一样
: 这个是典型的递归
|
a**********0
发帖数: 422 | 12 我想错了
【在 l*********8 的大作中提到】
: S = "ababca", T="aa"这个例子
: count[0][0], count[1][0]... count[5][0]的值是：
: 1 1 2 2 2 3
: count[0][1], count[1][1]... count[5][1]的值是：
: 0 0 1 1 1 3
: 递推:(没写边界情况）
: if (S[i] == T[j])
: count[i][j] = count[i-1][j] + count[i-1][j-1];
: else
: count[i][j] = count[i-1][j];
|
