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 }