# APCS實作題2022年1月第3題：數位占卜

> 日期：2024年8月1日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=h083)

## 題目

### 問題描述

占卜籤筒有 $m$ 支籤，每一支籤為一個由英文小寫字母組成的字串。從籤筒內抽出兩支籤，若將這兩支籤上的字串 $S$ 和 $T$ 連接起來形成的字串可以將該字串拆成左右兩半並且內容一樣，則抽到聖筊代表神明同意，否則神明不同意或是沒回答。

例如抽出的兩支籤上的字串分別為 piep 和 ie，則相連接起來的字串為 piepie 可以拆分左右兩半為相同的字串 pie 和 pie，但抽出的兩支籤為 foo 和 bar 時則不滿足條件。

神奇的是，若抽到的兩支籤 $S$ 和 $T$ 為聖筊，則不管是將 $T$ 接在 $S$ 後面或是順序反過來接起來，都可以是聖筊，再次說明了這兩支籤有著某種神秘力量在祝福著抽到的幸運人。例如 piep 和 ie 不管是使用 piepie 或是 iepiep 都可以拆分成兩個一樣的字串。

詢問籤筒內這 $m$ 支籤，有幾個 pair 可以形成聖筊。相同的兩支籤組合計算一次即可。
<br />

### 輸入說明

輸入一個正整數 $m$，接下來有 $m$ 的字串，每個字串長度最長為 $100$。

數字範圍
- $1 \leq m \leq 50000$
- 籤筒內所有字串均相異

子題配分
- 20%：$2 \leq m \leq 100$，字串長度只會是 10 或是 20。
- 20%：字串長度只會是 10 或是 20
- 60%：無額外限制

<br />

### 輸出格式

輸出一個正整數，代表有幾個 pair 滿足條件。
<br />

### 範例輸入1

3
a
aba
aaa

### 範例輸出1

1

### 範例輸入2

5
abyyyab
y
yy
yyy
yyyy

### 範例輸出2

3

<br /><br />

## Python 程式碼

### 寫法1，暴力解，會超時

到第4筆測資時會超時。

m = int(input())  # 字串數量
words = []  # 所有的字串
for _ in range(m): words.append(input())  # 讀取所有的字串

ans = 0  # 答案
for i in range(m):  # 依序産生 0 ~ m-1
    s = words[i]  # 字串 s
    for j in range(i+1, m):  # 依序産生 i+1 ~ m-1
        t = words[j]  # 字串 t
        st = s+t  # 組合 s+t
        n = len(st)  # st 長度
        if n&1: continue  # 如果長度是奇數，不符合要求，找下一個
        if st[:n//2] == st[n//2:]: ans += 1  # 如果符合要求，ans 加 1

print(ans)  # 印出答案

<br /><br />

### 寫法2，利用 set 加速

解題關鍵在於第9 ～ 14行，若以 abyyyab 為例，執行第9 ~ 14行的結果依序為

j = 1, left = a, right = b
j = 2, left = ab, right = ab, target = yyy
j = 3, left = aby, right = yab

費時最久約為 2.4 s，使用記憶體最多約為 12.7 MB，通過測試。

m = int(input())  # 字串數量
words = []  # 所有的字串
for _ in range(m): words.append(input())  # 讀取所有的字串
wordSet = set(words)  # 儲存所有字串的 set，判斷 set 之中是否有 target 的速度較快
ans = 0  # 答案

for s in words:  # 依序讀取字串存入 s
    n = len(s)  # s 的長度
    for j in range(1, n//2+1):  # 分割子字串的索引值，最多切到正中央
        left = s[:j]  # 左側子字串
        right = s[n-j:]  # 左側子字串
        if left == right:  # 如果左、右子字串相同
            target = s[j:n-j]  # 剩下的部分是符合條件的目標字串
            if target in wordSet: ans += 1  # 如果 target 在 wordSet 之中，ans 加 1
            #if target in words: ans += 1  # 速度較慢，會超時

print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，暴力解，會超時

到第4筆測資時會超時。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int m; cin >> m;  // 字串數量
    vector<string> words (m);  // 所有的字串
    for(int i=0; i<m; i++) cin >> words[i];  // 讀取所有的字串

    long long ans = 0;  // 答案，用 int 會溢位
    for(int i=0; i<m; i++) {  // 依序産生 0 ~ m-1
        string s = words[i];  // 字串 s
        for(int j=i+1; j<m; j++) {  // 依序産生 i+1 ~ m-1
            string t = words[j];  // 字串 t
            string st = s+t;  // 組合 s+t
            size_t n = st.size();  // st 長度
            if (n&1) continue;  // 如果長度是奇數，不符合要求，找下一個
            if (st.substr(0, n/2) == st.substr(n/2, n/2)) ans++;  // 如果符合要求，ans 加 1
        }
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，利用 set 加速

費時最久約為 0.8 s，使用記憶體最多約為 13.8 MB，通過測試。

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int m; cin >> m;  // 字串數量
    vector<string> words (m);  // 所有的字串
    set<string> wordSet;  // 儲存所有字串的集合
    for(int i=0; i<m; i++) {  // 讀取所有的字串
        cin >> words[i];
        wordSet.insert(words[i]);
    }

    long long ans = 0;  // 答案，用 int 會溢位
    for(string s : words) {  // 依序讀取字串 s
        size_t n = s.size();  // 字串 s 長度
        for(size_t j=1; j<=n/2; j++) {  // 依序産生 1 ~ n/2
            string left = s.substr(0, j);  // 左側子字串
            string right = s.substr(n-j, j);  // 右側子字串
            if (left == right) {  // 如果左、右子字串相等
                string target = s.substr(j, n-2*j);  // 剩下的部分是目標字串
                ans += wordSet.count(target);  // 如果 target 在 wordSet 之中 ans 加 1
            }
        }
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`