占卜籤筒有 M 支籤，每一支籤為一個由英文小寫字母組成的字串。從籤筒內抽出兩支籤，若將這兩支籤上的字串 S 和 T 連接起來形成的字串可以將該字串拆成左右兩半並且內容一樣，則抽到聖筊代表神明同意，否則神明不同意或是沒回答。
例如抽出的兩支籤上的字串分別為 piep 和 ie，則相連接起來的字串為 piepie 可以拆分左右兩半為相同的字串 pie 和 pie，但抽出的兩支籤為 foo 和 bar 時則不滿足條件。
神奇的是，若抽到的兩支籤 S 和 T 為聖筊，則不管是將 T 接在 S 後面或是順序反過來接起來，都可以是聖筊，再次說明了這兩支籤有著某種神秘力量在祝福著抽到的幸運人。
例如：piep 和 ie 不管是使用 piepie 或是 iepiep 都可以拆分成兩個一樣的字串。
詢問籤筒內這 M 支籤，有幾個 Pair 可以形成聖筊。相同的兩支籤組合計算一次即可。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 輸入一個正整數 M，接下來有 的字串，每個字串長度最長為 100。 | 輸出一個正整數，代表有幾個 Pair 滿足條件。 |
| 3 a aba aaa | 1 |
| 5 abyyyab y yy yyy yyyy | 3 |
解題思路
收字串的時候使用 Map 或 Set 來存哪些字串出現過。之後一個字串一個字串判斷，用 For迴圈 從 0 跑到字串的一半 +1 (因為要 Substring)，確認這個字串的第 0 個到第 i 個字元是否等於這個字串的最後 i 個字元，如果相等的話就判斷中間的字元有沒有在輸入時出現過，如果有的話答案就 +1，最後輸出答案即可。如果 Substring 太多次的話可能會 TLE 所以需要優化一下避免太多次的 Substring。
範例程式碼－ZeroJudge H083: 數位占卜
#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";
}
//ZeroJudge H083
//Dr. SeanXD