算法分析

　　乍看之下，本题似乎无从下手。但我们可以从解的生成过程中得到一些启示。
　　显然，初始时S1，S2均为空串。产生解的过程可分为若干步，每步选择一个串插在S1或S2的末尾，那么每个中间状态可以描述成下图所示。

　　　　　　　　　　　　　　　

　　其中A为已匹配的部分，B为未匹配的部分。且B是某个数字串的后缀。这样我们可以定义状态d[i,j]为：
　　当B部分为第i个数字串的后缀word[i,j+1..length[i]]时，A部分的最短长度。其中，word[i]表示第i个串，length[i]为第I个串的长度。
　　我们发现，其实后面的状态转移与A部分无关，仅与B部分有关。因此，我们可以用动态规划的方法来解决这道题。问题转化为求最短路。

　　初始时，
　　　　　

　　从某个状态d[i,j]出发进行转移，可以分为两种情况：
　　　　1 存在某个串word[k]是word[i,j+1..length(s)]的前缀，则
　　　　　　d[i,j+length[k]] = min{ d[i,j+length[k]]，d[i,j]+length[k]}
　　　　2 存在某个串word[k]，使得word[i,j+1..length(s)] 是word[k]的前缀，则
　　　　　　d[k,length[i]-j] = min { d[k,length[i]-j]，d[i,j]+length[i]-j}

　　最后的解是所有d[k,length[k]](k=1..n)中最小的一个。

　　需要特别指出的是上面min函数的定义。因为题目要求找出的串是长度最短且在同长度的串中字典序最小的一个，因此，若长度不等时，可以直接取小的那个；若长度相等，则要追溯前面的状态，取字典序较小的那个。这与一般的动态规划是不太相同的，需要特别注意。

关于实现的说明

　　本题可以采用经典的求最短路算法来实现，但因为有可能要追溯前面的状态，为了编程方便，可以采用记忆化搜索的方式。
　　另外，由于程序中需要大量用到查找某个字符串是否存在的操作，为了提高程序效率，我们可以用检索树的结构来存储，具体的方法参见数据结构的书中的有关章节。

小结

　　这是一道图论问题，但不经过仔细分析，不太容易看出模型。这就要求我们熟练的掌握各种基本算法，同时对题目进行深入的研究。另外，灵活运用一些高级数据也对提高程序效率有着很大帮助。