上一道题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

上一道题

上一道题# JobHunting - 待字闺中

p*22012-03-27 07:03

1 楼

一个String有sub string 和 sub sequence.
sub string大家都知道，sub sequence就是可以不连续的sub string。
比如abc, ab, bc 都是substring, 而ac不是。但是，ac也是sub sequence。
现在给两个String， s和t
那么在s里选取一个substring，在t里选取一个sub sequence，使得他们相等。
问可以选取多少种组合。sub string , sub sequence 内容相等不要紧，只要有字符的
位置不同就认为是不同的string。
比如
s: "aa"
t: "aa"
ans: 5

s*n2012-03-27 07:03

2 楼

很难，面试遇到就投降了

g*e2012-03-27 07:03

3 楼

暴力数？

p*22012-03-27 07:03

4 楼

暴力不行。这是到DP题。代码量很少。

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

: 暴力数？

l*e2012-03-27 07:03

5 楼

用DP, 复杂度n3

a*g2012-03-27 07:03

6 楼

n^2吧

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

: 用DP, 复杂度n3

p*22012-03-27 07:03

7 楼

大牛给讲一讲。

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

: n^2吧

z*c2012-03-27 07:03

8 楼

我的想法
F[i][j]为S的substring最后取得位置是i，T的sub sequence最后取得位置是j，匹配的
方案数
1. S[i]!=T[j]，则F[i][j]=0
2. S[i]==T[j]，则
a. i和j分别都是各自的第一个字符，方案数1
b. i和j不是第一个字符，那么方案数F[i - 1][k] k < j
so
F[i][j] = 1 + sum (F[i - 1][1] + F[i - 1][2] .. F[i][j - 1])
设
S[i][j] = F[i][1] + F[i][2] + ... F[i][j]
所以
F[i][j] = 1 + S[i - 1][j - 1]
S[i][j] = S[i][j - 1] + F[i][j]
answer = sigma (F[i][j]), i <= len (s), j <= len(t)

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

: n^2吧

p*22012-03-27 07:03

9 楼

你这么牛还需要多准备一个星期面F吗？

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

: 我的想法
: F[i][j]为S的substring最后取得位置是i，T的sub sequence最后取得位置是j，匹配的
: 方案数
: 1. S[i]!=T[j]，则F[i][j]=0
: 2. S[i]==T[j]，则
: a. i和j分别都是各自的第一个字符，方案数1
: b. i和j不是第一个字符，那么方案数F[i - 1][k] k < j
: so
: F[i][j] = 1 + sum (F[i - 1][1] + F[i - 1][2] .. F[i][j - 1])
: 设

z*c2012-03-27 07:03

10 楼

您搞笑了，刚才的G电面就跟坨屎一样。。。

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

:
: 你这么牛还需要多准备一个星期面F吗？

h*62012-03-27 07:03

11 楼

楼主你的F面完了吗，我刚去了估计没戏。

i*e2012-03-27 07:03

12 楼

应该不会吧，以你的实力来看的话。

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

: 楼主你的F面完了吗，我刚去了估计没戏。

a*g2012-03-27 07:03

13 楼

M[i, j]: 以s[i]为结束的substring匹配t[0-j]的方案数
case 1: s[i] == t[j]
M[i, j] = M[i-1, j-1] + M[i, j-1] + 1
case 2: s[i] != t[j]
M[i, j] = M[i, j-1]
最后结果为: M[0, n-1] + M[1, n-1] + ... + M[n-1, n-1]
对么？

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

: n^2吧

p*22012-03-27 07:03

14 楼

这题对我来说太复杂了。看了你的解释才有点头绪。晚上在好好看看。

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

b*e2012-03-27 07:03

15 楼

This seems to be O(n^3). I believe there's O(n^2).

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

S*t2012-03-27 07:03

16 楼

Arxor?

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

: 您搞笑了，刚才的G电面就跟坨屎一样。。。

p*22012-03-27 07:03

17 楼

费了老半天劲写了一个恶心的。
int[][] dp = new int[2][];
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
char[] s = in.next().toCharArray();
char[] t = in.next().toCharArray();
int slen = s.length;
int tlen = t.length;
int mod = 1000000007;
dp[0] = new int[tlen];
dp[1] = new int[tlen];
int total = 0;
for (int j = 0; j < tlen; j++)
{
if (s[0] == t[j])
{
total++;
dp[0][j] = 1;
}
}
for (int i = 1; i < slen; i++)
{
if (s[i] == t[0])
{
dp[1][0] = 1;
total++;
}
int sum = 0;
for (int j = 1; j < tlen; j++)
{
sum += dp[0][j - 1];
sum %= mod;
if (s[i] == t[j])
{
dp[1][j] = sum + 1;
total += sum + 1;
total %= mod;
}
}
int[] tmp = dp[0];
dp[0] = dp[1];
dp[1] = tmp;
Arrays.fill(dp[1], 0);
}
out.println(total);
out.close();
}