AcWing 779. 最长公共字符串后缀
原题链接
困难
作者:
我就是废物
,
2021-01-17 17:54:32
,
所有人可见
,
阅读 302
C++ 代码
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin>>n,n)
{
string a[n]; //用string数组来保存每行字符串
for(int i=0;i<n;i++)
cin>>a[i];
int m=200,p=0;
for(int i=1;i<n;i++) //找出最短的字符串,记录长度m和位置p(可以并入上面读入操作同时进行)
{
if(a[i].size()<m)
{
m=a[i].size();
p=i;
}
}
string s=a[p]; int i; //s即最短字符串,i+1记录最长公共后缀长度。
for(i=0;i<m;i++) //只需要枚举i在[0,m)的整数。
{
int j;
for(j=0;j<n;j++) //枚举string数组a[]的每一个元素(即每一行字符串),判断公共后缀是否匹配
if(a[j][a[j].size()-1-i]!=s[m-1-i]) break; //一旦不匹配,终止枚举
if(j!=n) break; //若j=n,表示每个字符串的(长度-1-i)位置是匹配的,再枚举i+1。否则,终止枚举
}
if(i==0) cout << endl; //i=0表示没有公共后缀
else cout << s.substr(m-i,i) << endl; //i>0,表示有长度为i的最长公共后缀
}
return 0;
}