题目描述
给定一个由小写字母构成的字符串 s。
请你找到一个满足如下所有要求的字符串 t:
字符串 t 是字符串 s 的前缀。
字符串 t 是字符串 s 的后缀。
字符串 t 在字符串 s 的中间出现过。也就是作为一个既非前缀也非后缀的子串出现过。
字符串 t 的长度应尽可能长。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据占一行,包含一个字符串 s。
输出格式
每组数据输出一行结果,如果 t 存在,则输出 t,否则输出 not exist。
数据范围
前三个测试点满足 1≤|s|≤20。
所有测试点满足 1≤T≤10,1≤|s|≤106。
同一测试点内所有输入字符串 s 的长度之和不超过 106。
样例
输入样例:
2
fixprefixsuffix
abcdabc
输出样例:
fix
not exist
算法1
(kmp-next) $O(n)$
1.kmp算法next数组
以n为结尾的。与前缀匹配的。
最长:$ next[n] $
次长:$ next[next[n]] $
次次长: $ next[next[next[n]]] $
2.感谢聪明睿智的y总讲课
跟着y总学算法,很感谢
3.比较low,next数组啥的,代码风格,方法是比较笨的写法。但是方便自己理解。
大佬勿喷。只是分享一下代码。
时间复杂度
参考文献
python3 代码
from typing import List
#----kmp求next数组
def get_next(b: str) -> List[int]:
n = len(b)
next = [0 for _ in range(n + 1)] #用虚指
next[0] = -1
l = -1
r = 0
while r < n:
if l == -1 or b[l] == b[r]:
l += 1
r += 1
next[r] = l
else:
l = next[l]
return next
T = int(input())
for _ in range(T):
s = input()
n = len(s)
next = get_next(s)
visited = [False for _ in range(n)]
#前面n-1位,出现过的,与前缀匹配的长度
for i in range(1, n): #是虚指。最后一位是n,不visit
visited[next[i]] = True
res = 0
x = next[n]
while x > 0:
if visited[x] == True:
res = x
break
x = next[x]
if res > 0:
print(s[ :res])
else:
print("not exist")
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//----获取kmp的next数组
vector<int> get_next(string & b)
{
int n = (int)b.size();
vector<int> next(n + 1, 0); //虚指
next[0] = -1;
int l = -1;
int r = 0;
while(r < n)
{
if (l == -1 || b[l] == b[r])
{
l ++;
r ++;
next[r] = l;
}
else
{
l = next[l];
}
}
return next;
}
int main()
{
int T; cin >> T;
while (T -- )
{
string s; cin >> s;
int n = (int)s.size();
vector<int> next = get_next(s);
bool visited[n];
memset(visited, 0, sizeof(visited));
//---前n-1个位置,与前缀匹配的长度。虚指。
for (int i = 1; i < n; i ++)
visited[next[i]] = true;
int res = 0;
int x = next[n];
while (x > 0)
{
if (visited[x] == true)
{
res = x;
break;
}
x = next[x];
}
if (res == 0)
cout << "not exist" << endl;
else
cout << s.substr(0, res) << endl;
}
return 0;
}
java 代码
import java.util.* ;
import java.io.* ;
public class Main
{
public static void main(String [] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while (T -- > 0)
{
String s = br.readLine();
int n = s.length();
int [] next = get_next(s);
boolean [] visited = new boolean[n];
for (int i = 1; i < n; i ++)
visited[next[i]] = true;
int res = 0;
int x = next[n];
while (x > 0)
{
if (visited[x] == true)
{
res = x;
break;
}
x = next[x];
}
if (res == 0)
System.out.println("not exist");
else
System.out.println(s.substring(0, res));
}
}
public static int [] get_next(String b)
{
int n = b.length();
int [] next = new int [n + 1];
next[0] = -1;
int l = -1;
int r = 0;
while (r < n)
{
if (l == -1 || b.charAt(l) == b.charAt(r))
{
l ++;
r ++;
next[r] = l;
}
else
{
l = next[l];
}
}
return next;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla