AOJ鏈接： 最大公共子串
這道題求多個字符串的最大公共序列（非連續(xù)）的長度，題目中說明了所有串的乘積不超過30000；
題解將狀態(tài)記錄在一個長度為30000的數(shù)組中，使用類似編碼的方式（我的理解）進行存取；
和算法導論上對LCS的解法不大一樣（遞歸而不是遞推，計算量會少一些），仍然是動態(tài)規(guī)劃的思想；
0MS，學習了。
下面的代碼是看懂了書上的后，自己寫的；
起先覺得第47、48行的恢復多余，后來發(fā)現(xiàn)并不是：包含回溯的過程，需要恢復原來的下標。
1
# include <stdio.h>
2
# include <
string
.h>
3
4
char
str[
102
][
102
];
5
int
c[
30005
];
6
int
tmp[
102
];
7
int
len[
102
];
8
9
int
get
(
int
n,
int
*x);
10
11
int
main()
12
{
13
int
T, N, i;
14
15
scanf(
"
%d
"
, &T);
16
while
(T--)
17
{
18
scanf(
"
%d
"
, &N);
19
memset(c,
0xff
,
sizeof
(c));
20
for
(i =
1
; i <= N; ++i)
21
{
22
scanf(
"
%s
"
, str[i]);
23
tmp[i] = len[i] = (
int
)strlen(str[i]);
24
}
25
printf(
"
%d\n
"
,
get
(N, tmp));
26
}
27
28
return
0
;
29
}
30
31
int
get
(
int
n,
int
*x)
32
{
33
int
i, j, index, ret, rem;
34
35
for
(i =
1
; i <= n; ++i)
36
if
(x[i] ==
0
)
return
0
;
37
for
(i = n-
1
, index = x[n]-
1
; i >=
1
; --i)
38
index = index*len[i] + x[i]-
1
;
39
if
(c[index] >=
0
)
return
c[index];
40
for
(i =
2
; i <= n; ++i)
41
if
(str[
1
][x[
1
]-
1
] != str[i][x[i]-
1
])
break
;
42
if
(i > n)
43
{
44
for
(j =
1
; j <= n; ++j)
45
--x[j];
46
ret =
get
(n, x) +
1
;
47
for
(j =
1
; j <= n; ++j)
48
++x[j];
49
}
else
50
{
51
ret =
0
;
52
for
(j =
1
; j <= n; ++j)
53
{
54
--x[j];
55
rem =
get
(n, x);
56
if
(rem > ret) ret = rem;
57
++x[j];
58
}
59
}
60
c[index] = ret;
61
return
ret;
62
}
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
