题目描述
给定一个串，如ABCDAB，则ABCDAB的真前缀有：{ A, AB,ABC, ABCD, ABCDA }ABCDAB的真后缀有：{ B, AB,DAB, CDAB, BCDAB } 因此，该串的真前缀和真后缀中最长的相等串为AB，我们称之为该串的“最长的真前后缀”。试实现一个函数string matched_Prefix_Postfix(string str)，得到输入串str的最长的真前后缀。若不存在最长的真前后缀则输出empty
输入
第1行：串的个数 n第2行到第n+1行：n个字符串
输出
n个最长的真前后缀，若不存在最长的真前后缀则输出empty。
输入样例1
6 a ab abc abcd abcda abcdab
输出样例1
empty empty empty empty a ab
思路分析
KMP算法不仅仅可以用了求子串，它的next值有着非常丰富的应用。
我们首先来求next的值，下标从1开始的话，next【0】存的是子串的长度，下一个next值需要根据前一个next值来确定，首先判断当前字符的前面所组成的字符串的前后缀（前一个字符和第一个字符）是否是相同的字符，如果相同，那么当前字符的next值为前一个next值+1，如果不同，继续比较前一个字符和前一个next值所对应的字符是否相同，如果都不相同，那么next值为1。
但是看代码可以知道，我们拓展了字符串，这是因为要求出最后一个字符对应的next值。
字符串的最长的真前后缀就是从第一个字符串开始连续最后一个next值数目（下标从0开始，下标从1开始需要减1）的子串。
AC代码
#include <bits/stdc++.h>using namespace std;
string matched_Prefix_Postfix(string str) {
str+='#';
int next[str.size() + 1];
next[0] = str.size();
next[1] = 0;
int i = 2, j = 0;
while (i <= next[0]) {
if (j == 0 || str[i - 2] == str[j - 1]) {
next[i] = j + 1;
i++;
j = next[i - 1];
} else j = next[j];
}
if (next[str.size()] <= 1)
return "";
return str.substr(0, next[str.size()]-1);
}
int main() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
if (matched_Prefix_Postfix(str) != "")cout << matched_Prefix_Postfix(str) << endl;
else cout << "empty" << endl;
}
}
