ZeroJudge H083: 數位占卜

題目敘述

每筆測資第一行有一個正整數N，接下來會有N行字串，每個字串都是由小寫英文字母組成，無空格。要求輸出有多少對字串 (兩個) 加在一起之後切一半兩邊都是一樣的。

範例輸入 #1

3

a

aba

aaa

範例輸出 #1

1

範例輸入 #2

5

abyyyab

y

yy

yyy

yyyy

範例輸出 #2

3

解題思路

收字串的時候使用Map或Set來存哪些字串出現過。之後一個字串一個字串判斷，用For迴圈從0跑到字串的一半+1 (因為要Substring)，確認這個字串的第0個到第i個字元是否等於這個字串的最後i個字元，如果相等的話就判斷中間的字元有沒有在輸入時出現過，如果有的話答案就+1，最後輸出答案即可。如果Substring太多次的話可能會TLE所以需要優化一下避免太多次的Substring。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    unordered_map<string, int>MAP;
    string s[60000] = {};
    for (int i = 0; i<N; i++)
    {
        cin >> s[i];
        MAP[s[i]]++;
    }
    int ans = 0;
    for (int i = 0; i<N; i++)
    {
        string str = s[i];
        for (int j = 1; j<(int(str.length())/2)+1; j++)
        {
            string ascertain = str.substr(j, str.length() - j - j);
            string initial = str.substr(0, j);
            string terminal = str.substr(str.length()-j, str.length());
            if (initial == terminal)
            {
                if (MAP[ascertain] >= 1)
                {
                    ans++;
                }
            }
        }
    }
    cout << ans << "\n";
}