题目描述
给出若干个字符串,输出这些字符串的最长公共后缀。
输入格式
由若干组输入组成。
每组输入的第一行是一个整数N。
N为0时表示输入结束,否则后面会继续有N行输入,每行是一个字符串(字符串内不含空白符)。
每个字符串的长度不超过200。
输出格式
共一行,为N个字符串的最长公共后缀(可能为空)。
数据范围
1≤N≤200
输入样例:
3
baba
aba
cba
2
aa
cc
2
aa
a
0
输出样例:
ba
a
算法1
(暴力枚举)
C++ 代码
#include <iostream>
using namespace std;
string str[210]; //字符串数组
int main(){
int n;
while (cin >> n , n ){
int cnt[210]={0}; //用来记录每行字符串跟第一个字符串有几个元素是相同的
for(int i=0;i<n;i++){ //自己一开始把cnt当作全局变量导致没有做出来
cin >> str[i] ; //自己用getline(cin,str[i])读入会报错
} //是因为getline不会吸收回车如果用getline的话
int minlen = 300; //要在getline前面加一个scanf("\n");来吸收回车
for(int i=0;i<n;i++){ //找到字符串数组中长度最小的字符串长度是多少
int x=str[i].size(); //这样每一次比较公共部分的长度就会节省时间
if( x < minlen )
minlen = x;
}
for(int i=0;i<n;i++){ //将字符串颠倒顺序
string temp; //即将后缀的比较变成前缀的比较
for(int j=(str[i].size() - 1); j >=0; j--){
temp += str[i][j];
}
str[i]=temp;
}
for(int i=1;i<n;i++){ //将每一行的字符串与第一行的字符串比较
for(int j=0; j < minlen ; j++){
if ( str[i][j] == str[0][j]) cnt[i]++;
else break;
}
}
int min=300; // min 表示这个共同前缀的最小长度
bool flag = true;
for(int i=1;i<n;i++){
if( cnt[i] == 0 ) { //有一项为0 代表至少有一个字符串没有公共部分
flag =false; //break 什么也不输出
break;
}
if( cnt[i] < min ) min = cnt[i];
}
if (flag){ //如果cnt数组每一项都不为0 表明一定有一个最小的公共部分
min -- ; //将其输出
string s1=str[0];
for(int i=min; i >=0; i -- ){
cout << s1[i] ;
}
}
cout << endl;
}
return 0;
}
做法2
#include<iostream>
using namespace std;
const int N =210;
int n;
string s[N];
int main()
{
while(cin >> n ,n)
{
int len = 300;
for(int i = 0; i < n ; i ++)
{
cin >> s[i];
if(len > s[i].size()) len = s[i].size();
}
while(len)
{
bool success = true;
for(int i = 1; i < n ; i ++ ) //将s[0]的后缀 与 s[1~n-1] 的后缀进行比较
{
bool is_same = true;
for(int j = 1; j <= len ; j ++)
if(s[0][s[0].size() - j] != s[i][s[i].size() - j]) //直接string类型做比较 更加简单
{
is_same = false;
break;
}
if(is_same == false )
{
success = false;
break;
}
}
if(success) break;
len -- ;
}
cout << s[0].substr(s[0].size()-len) << endl;
}
return 0;
}
注释好评