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;
}