Sicily1198 Substring题解
Oct 27, 2013题目传送门: http://soj.me/1198
题意很简单，给出n个字符串，如何拼接这n个字符串，使得得到的字符串字典序最小。
Solutions
这题一个很容易想到但是错误的做法是直接字符串排序，然后拼接起来，这个做法看起来是正确的，但实际是错误，看下面的一个反例:
|
|
按照直接排序得到结果是bba, 但正确答案是bab.
由于题目只有8个字符串，可以直接使用暴力枚举,8!
有一个更好的方法，适用于n更大的情况, 也是对字符串进行排序，但是排序的cmp函数改为如下：
|
|
然后按照排序结果连接起来即可，
但这个算法的正确性需要依赖传递性(ab<=ba, bc<=cb => ac<=ca)，具体证明见下一节。
传递性证明
有下面定理1：
有字符串a,b, 且a < b(字符串比较)
ab <= ba <=> a+…+a <= b+…+b(字符串是无限长)
证明：
充分性
|
|
|
|
综合(1),(2),(3), 得到：
aa....aa <= ab....ab <= baba..ba <= bb....bb, 得证。
必要性
证明：
a <= b, a+a+…+a <= b+…+b, => ab <= ba
分三种情况：
1) len(a) = len(b)
由 a<=b，结论ab <= ba明显成立。
2) len(a) > len(b)
a<=b => a.substr(0, len(b)) < b, 易证ab <= ba
3) len(a) < len(b)
这种情况证明比较麻烦， 可以分为两种子情况：
3.1) a不是b的前缀，即a.substr(0, len(b)) != b
由a <= b, 可以得出a.substr(0, len(b)) < b, => ab < ba.
3.2) a是b的前缀，即a.substr(0, len(b)) == b
这种情况是整个证明中最难理解和困难的地方。
由a+…+a <= b+…+b, 必然下面两个字符串满足：
aa…aa <= b…b, (左右两边字符串长度相等，总的总长度为len(a)*len(b))
结合上面的不等式，查看下面这幅图：
因为a是b的前缀，所以
b可以由b1和bn-1两部分组成, b=b1+bn-1, 其中b1=a。
接着a和bn-1对齐接着比较，那么bn-1 = b2+bn-2, 这时可以判断b2 ?< a, 若b2=a, 可以接着划分下去n-3,n-4，直到结尾或得到大小比较。
用形式化语言可以这样说：
假设b=b1b2b3…bi…bn, len(bi) = len(a), len(bn) <= len(a), bn是a的前缀
由aa…aa <= bb…bb, 推出
存在i > 0，使得a <= bi, bj = a(j < i).
查看下面ab和ba的字符串比较，查看下面这幅图：
a对应b1,
b1对应b2,
b2对应b3,
…
bi-1对应bi,
…
bn-1+bn对应bn+a
由上述推论得到：
存在一个i，使得a = bi-1 <= bi, a+b1+b2+...+bi-1+...+bn <= b1+b2+b3+...+bi+bn+a，
即 ab <= ba。
由上述1), 2), 3),结论成立。
由定理1可以推出下面结论，传递性:
字符串a,b,c, 若 ab <= ba, bc <= cb
则有ac <= cb
证明：
|
|
取total_len = len(a)*len(b)*len(c)， 则有：
|
|