晴神机试模拟题选解

晴神机试模拟题选解题目一：next[i]在字符串匹配的KMP算法中有一个重要的概念是next数组，求解它的过程让不少同学伤透了心。next数组的直接语义其实是：使“长度为L的前缀”与“长度为L的后缀”相同的最大L，且满足条件的前后缀不能是原字符串本身。例如对字符串"ababa"来说，长度为1的前缀与后缀都是"a"，它们相同；长度为2的前缀与后缀分别是"ab"和"ba"，它们不相同；长度为3的前缀与后缀都是"aba"，它们相同；长度为4的前缀与后缀分别是"abab"和"baba"，它们不相同。因此对字符串"ababa"来说，使“长度为L的前缀”与“长度为L的后缀”相同的最大L是3。现在我们把这个最大的L值称为原字符串S的next值。在此概念的基础上，对给定的字符串S，下标为从1到N，那么next[i]就是指子串S[1…i]的next值。现在给定一个字符串，下标从1到N，然后给一个下标i，求next[i]。输入每个输入文件一组数据。只有一行，输入一个仅由小写字母组成的长度为N（1=N=100）的字符串、与一个下标i（1=i=N）。输出一个整数，即next[i]。Sample Input 1ababa 5Sample Output 13Sample Input 2ababab 4Sample Output 22Sample Input 3ab 2Sample Output 30Note：说是求next数组，其实一水题