779. 最长公共字符串后缀

文章目录

• ​​Question​​
• ​​Ideas​​
• ​​Code​​

Question

给出若干个字符串，输出这些字符串的最长公共后缀。

输入格式

由若干组输入组成。

每组输入的第一行是一个整数 N。

N 为 0 时表示输入结束，否则后面会继续有 N 行输入，每行是一个字符串（字符串内不含空白符）。

每个字符串的长度不超过 200。

输出格式

共一行，为 N 个字符串的最长公共后缀（可能为空）。

数据范围

1≤N≤200

输入样例：

3

baba

aba

cba

2

aa

cc

2

aa

a

输出样例：

ba

Ideas

1. 枚举尾缀的长度
2. 判断每个字符串的尾缀是否相等

1. 枚举每个字符串
2. 枚举每个字符的字符

Code

// 枚举:从大到小遍历尾缀的长度，然后逐个字符串比对他们的尾缀是否相等
#include <iostream>
#include <string>
#define N 210

using namespace std;
string ss[N];


int main()
{
    int n;
    string s;
    while (cin >> n, n)
    {
        // 确定最大的尾缀的长度，即字符串的最小长度
        int len = 1000;
        for (int i = 0; i < n; i ++)
        {
            cin >> ss[i];
            if (len > ss[i].size()) len = ss[i].size();
        }
   
        // 遍历长度
        while (len)
        {
            bool is_sucess = true;
            // 遍历所有的字符串
            for (int i = 1; i < n; i ++)
            {
                bool is_same = true; // 判断当前长度的尾缀是否符合条件flag
                // 遍历每个字符串的字符
                for (int j = 1; j <= len; j ++)
                {
                    
                    if (ss[0][ss[0].size()-j] != ss[i][ss[i].size()-j])
                    {
                        is_same = false;
                        break;
                    }
                }
                
                if (!is_same)
                {
                    is_sucess = false;
                    break;
                }
            }
            if (is_sucess) break;
            
            len--;
        }
        cout << ss[0].substr(ss[0].size()-len,ss[0].size()) << endl;
        
        
    }
    return 0;
}