(暴力枚举) $O(n^2)$
输入的时候就直接把每个字符串翻转一下,题目就变成了求最长前缀,对于每个字符串同时进行逐个字母的判断,最终结果进行一次reverse
就是答案
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int main()
{
int n;
while (cin >> n, n)
{
string ss[N], res;
int min_len = N;
for (int i = 0; i < n; i ++)
{
string s;
cin >> s;
int len = s.size();
min_len = min(min_len, len);
reverse(s.begin(), s.end());
ss[i] = s;
}
for (int i = 0; i < min_len; i ++)
{
char c;
bool equ = true;
for (int j = 0; j < n; j ++)
{
if (!j)
c = ss[j][i];
else
{
if (c != ss[j][i])
{
equ = false;
break;
}
}
}
if (equ) res.push_back(c);
else break;
}
reverse(res.begin(), res.end());
cout << res << endl;
// for (int i = 0; i < n; i ++) cout << ss[i] << endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
while (cin >> n, n)
{
string strs[n];
int min_len = 210;
for (int i = 0; i < n; i ++)
{
string s;
cin >> s;
reverse(s.begin(), s.end());
min_len = min(min_len, (int)s.size());
strs[i] = s;
}
string res;
for (int i = 0; i < min_len; i ++)
{
char c = strs[0][i];
bool flag = true;
for (string s : strs)
if (s[i] != c)
{
flag = false;
break;
}
if (flag) res += c;
else break;
}
reverse(res.begin(), res.end());
cout << res << endl;
}
return 0;
}
python3 代码
while True:
n = int(input())
if n == 0:
break
strs = []
min_len = 210
for i in range(n):
s = input()[::-1]
min_len = min(min_len, len(s))
strs.append(s)
res = ''
for i in range(min_len):
c = strs[0][i]
flag = True
for s in strs:
if s[i] != c:
flag = False
break
if flag:
res += c
else:
break
print(res[::-1])