初次尝试刷题，当然要刷简单的啦。
455 - Periodic Strings
**问题描述：**求一个字符串的最小周期，例如"123123123"的最小周期为3。从数据规模来看，穷举法完全可行，但还是要学习一下这位老哥对KMP的巧妙运用：
设字符串A长度为s，求出整个字符串的最大border长度t。如果s-t | s，那么最小周期为s-t；否则，最小周期为s。
证明：如果s-t | s，那么A可以分为若干个长度为s-t的部分，叫做A1, A2, …, An。 最长border作为前缀时为A[1…n-1]，作为后缀时为A[2…n]。 因此，A1 = A2 = … = An，最小周期长度为s-t。
886 - Named Extension Dialing
**问题描述：**给一堆英文名字，都由两个单词组成，每个名字都有唯一的4位编号，例如Tirion Fordring 0303。现在有一个用户拿手机拨号，按照九键输入的方式拨出了若干个号码，问对于每个号码，有哪些名字能与之匹配，输出其编号。匹配的规则是，如果号码与某个编号一致，则成为唯一匹配并忽略其他匹配，否则寻找满足"the first letter of the first name followed by the first letters of the last name"的名字，例如8367对应"T For"，输出0303。
这本来是一道比较简单的题目。
- 初始化8个Trie树，分别对应九键键盘上的2-9，再初始化一个大小为10000的布尔数组number。
- 每读入一个名字，就把它翻译成2-9的数字
- 翻译后，若first name的首位为i，就在Trie[i]中插入last name，并在每个结点存储其编号，再令number[编号]=true。
- 对于每个号码，先查看number[号码]，若为true则直接输出该号码，匹配结束
- 否则，根据号码的第一位找到Trie树，然后用剩下的位走这个Trie树
- 如果能走到一个结点，说明可以匹配，该结点存储的所有编号就是匹配结果
构造Trie树的复杂度为last name的长度和，查找匹配的复杂度为号码的长度和。
然而我TM看错题了！！！
我把匹配条件看成了"the first letters of the first name followed by the first letters of the last name"。
于是在我眼里，这道题问的是，已知字符串A,B,P，请问P能否由A和B的各一个前缀组成。
我甚至把它做了出来，简要描述一下方法：求A与P的最长公共前缀长度lcp，再求B+P的前缀函数pf，从而求出B+P的最长、又不长于P的border（设长度为bd）。若len(P)-bd小于lcp，说明P长为bd的后缀是B的前缀，而剩下的前缀长度小于lcp，因此是A的前缀。
10298 - Power Strings
**问题描述：**和455完全一样，除了输入输出的要求。
由于UVa不给用户看自己交的代码，因此这道题之前的代码全都丢了。后面的题目解答我会保存下来，留作纪念。
11362 - Phone List
**问题描述：**给一堆字符串，问是否存在某个字符串是另一个的前缀。
用Trie树依次插入。如果路过叶子结点，或插入最后一个字符时没有新建结点，则答案为是，此后的所有输入可以不做处理。
11475 - Extend to Palindrome
**问题描述：**给一个字符串，往后面加最少的字符，使其成为回文串。
首先学习一下Manacher算法。该算法输入一个字符串s，输出两个数组d1和d2，d1[i]代表以s[i]为中心的奇数回文子串个数（包含s[i]自己），d2[i]代表以s[i]为中心的偶数回文子串个数。
- 算法记录了一个“边界”[l,r]，表示目前找到的最右边的回文子串，也就是让r最大
- 边界的初始值为[0,-1]
- 从左到右遍历s。由于只有遍历到边界中心才能算出边界，因此现在的位置i必定在边界中心的右侧
- 如果i已经超出边界，就采取简单算法：向两边依次扩张、比较，得到该位置的d1/d2值
- 如果i在边界内，就以边界中心为轴，找到该位置的对称点i2（边界中心的左侧）
- 由于边界本身是回文串，因此以i2为中心的、不超出边界的最长回文子串，也一定是以i为中心的、不超出边界的最长回文子串（无法保证边界外的对称性）
- 超出边界的部分，用简单算法求出
- 现在你可以发现为什么要记录，并且只需要记录最右的回文子串——因为能跳过最多的比较
int d1[n],d2[n];
// 奇数长度，中心唯一
for(int i=0,l=0,r=-1; i<n; i++) {
// k表示现在已知有几个以i为中心的回文子串
// 若i>r，不能利用边界内部的信息，因此k=1（中心本身）
// 否则，取 对称位置的d1值 与 中心到边界右侧的距离 的较小值
int k=(i>r)?1:min(d1[l+r-i],r-i); // r-i+1?
// 简单算法，将k增加为正确的d1值
// 每次都试图找到第k+1个回文子串，因此比较s[i-k]与s[i+k]
while(0<=i-k && i+k<n && s[i-k]==s[i+k]) k++;
// 赋值后，k需要减1，迎合下一步更新边界的计算
d1[i]=k--;
// 现在，以i为中心的最长子串为[i-k,j+k]
// 判断一下是不是需要更新一下边界
if(i+k>r) {l=i-k;r=i+k;}
}
// 偶数长度，规定中心处于偏右的位置
for(int i=0,l=0,r=-1; i<n; i++) {
// 中心本身还需要和自己左邻居比较，因此k最小为0（一个都不能跳过）
// 与对称回文子串的中心，应该是i的对称点的右邻居，因此是d2[l+r-i+1]
int k=(i>r)?0:min(d2[l+r-i+1],r-i+1);
while(0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k]) k++;
d2[i]=k--;
if(i+k>r) {l=i-k-1;r=i+k;}
}
现在来看这道题就非常简单了：在Manacher算法的过程中，每次更新边界时都检查r==s.length()-1。如果是，则可以终止循环，将此数组用到的l记录为x1和x2（有两个数组需要计算，初始值应该都是s.length()-1，代表最多从末尾添加起）。取x1和x2的较小值记为x，然后依次向字符串添加s[x-1]到s[0]的字符。
11576 - Scrolling Sign
**问题描述：**按顺序输入N个长度为len的小字符串，求最短的字符串S，使得这些小字符串都是S的子串，且第一次出现的位置不随着输入顺序递减。输出这个字符串的长度。（例如，ABCD/DEFG/DEFG/GGGG可以合并为ABCDEFGGGG）
我的方法：开足够大的字符数组，反向输入小字符串，两两之间插入’$’。从输入第二个字符串起，求当前位置开始、长度为2*len+1的子串，也就是str[i+1]+'$'+str[i]的border。这样就求出了前一个小字符串的后缀最多有多长，可以作为后一个小字符串的前缀。把这些求出的长度从N*len中减去，就得出了结果。
12467 - Secret Word
**问题描述：**给一个字符串S，要求找出最长的子串，使其倒置为S的某个前缀。
方法：构造字符串S+'$'+S2，其中S2为S的倒置，计算其前缀函数。在计算过程中，从S2起，记录出现的最大函数值maxbd及当前位置i。求出i的对称点mark = len-i-1，那么从该点开始、长度为maxbd的子串，就是要输出的结果。
11888 - Abnormal 89’s
**问题描述：**给一个字符串，判断它能不能由两个长度至少为2的回文串组成。如果不能，判断它是不是回文串。
。。。。。。
明天就开始上班了，有空补上。
总而言之，迈出了摆脱算法废柴的第一步，还是挺开心的，希望以后能继续进步。
