AOJ链接： 最大公共子串
这道题求多个字符串的最大公共序列（非连续）的长度，题目中说明了所有串的乘积不超过30000；
题解将状态记录在一个长度为30000的数组中，使用类似编码的方式（我的理解）进行存取；
和算法导论上对LCS的解法不大一样（递归而不是递推，计算量会少一些），仍然是动态规划的思想；
0MS，学习了。
下面的代码是看懂了书上的后，自己写的；
起先觉得第47、48行的恢复多余，后来发现并不是：包含回溯的过程，需要恢复原来的下标。
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
}
