题目描述
给出若干个字符串,输出这些字符串的最长公共后缀。
输入格式
由不超过 $5$ 组输入组成。
每组输入的第一行是一个整数 $N$。
$N$ 为 $0$ 时表示输入结束,否则后面会继续有 $N$ 行输入,每行是一个字符串(字符串内不含空白符)。
每个字符串的长度不超过 $200$。
输出格式
每组数据输出一行结果,为 $N$ 个字符串的最长公共后缀(可能为空)。
数据范围
$1≤N≤200$
输入样例
3
baba
aba
cba
2
aa
cc
2
aa
a
0
输出样例
ba
a
解法一:翻转字符串
解题思路
- 一组字符串的“最长公共后缀”一定是该组中“最短字符串”的后缀。
- 依次截取“最短字符串”的后缀,并与其他字符串的后缀进行匹配,每次截取的长度相较于上一次增加一个字符,即第 $1$ 次截取 $1$ 个字符,第 $2$ 次截取 $2$ 个字符。若第 $N$ 次截取的后缀与其他字符串的后缀匹配失败,则“最长公共后缀”为第 $N - 1$ 次截取的后缀。
- 由此可见,“最长公共后缀”需要使用“长度可变”的字符串变量进行存储,在Java语言中可以使用
String
或StringBuffer
进行实现,由于String
类的不可变性,每次操作都会创建新的字符串实例,而旧的字符串实例会被丢弃,从而产生大量临时垃圾,所以在这里选用StringBuffer
进行实现,在StringBuffer
类中的append()
方法是向字符串“后面”追加新的字符串,为了能够使用append()
方法,可以将读入的字符串使用StringBuffer
类中的reverse()
方法进行翻转,即将题目中求解的“后缀问题”转化为“前缀问题”。- 考虑到“最长公共后缀”可能为空,即输出“空字符”,可以考虑在读入字符串尾部插入“空字符”,经翻转后相当于在字符串的首部插入“空字符”,这样可以保证至少有一个“空字符”作为“最长公共后缀”,若录入的原字符串组并不存在“最长公共后缀”,则会直接输出“空字符”。
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int N = sc.nextInt();
if (N == 0) break;
StringBuffer strs[] = new StringBuffer[N];
StringBuffer res = new StringBuffer(" ");
int minLength = 200;
boolean flag = true;
String minLengthStr = " ";
for (int i = 0; i < N; i++) {
strs[i] = new StringBuffer(sc.next() + " ").reverse();
if (strs[i].length() < minLength) {
minLength = strs[i].length();
minLengthStr = strs[i].toString();
}
}
for (int i = 0; i < minLength; i++) {
for (int j = 0; j < N; j++) {
if (!strs[j].toString().startsWith(res.toString())) {
flag = false;
break;
}
}
if (flag) {
if (i + 1 < minLength) res.append(minLengthStr.charAt(i + 1));
else break;
} else {
res.deleteCharAt(res.length() - 1);
break;
}
}
System.out.println(res.reverse().toString().trim());
}
}
}