#apcs-202201-3 數位占卜
#c++
!!此程式並不是自己想出來的，程式出處請參照以下連結!!

1. 程式原理:
   假設有一個字串s="abyyyab"
   則我們可以將字串拆成這樣:
   |abyyy|ab|
   那我們要在後面加甚麼，使字串左右兩邊一樣?
   加上"yyy"對吧

   所以，當我抽到兩支籤 "abyyyab" 和 "yyy"，就會是聖筊

   再舉個例子
   s1="binarybin"，如果後面接上"ary"就會是聖筊
   ->binary|bin|ary
   那如果 s2="hyol"的話，後面只能接上和s2一樣的字才會聖筊
   ->hyol|hyol
   但是此題的所有字串都不同，所以它沒辦法聖筊
   我們可以發現，達成聖筊的條件就是
   後面的字和前面的字重複

   如:abyyyab, binarybin, hellohel
   他們都可以拆成
   abyyy|ab，binary|bin，hello|hel
   再回到第一個例子 "abyyyab" +"yyy"
   我們將其分成4部分:
   ab|yyy|ab|yyy
   A B A B
   可以發現 "abyyyab" +"yyy" 等同於 ABA + B
   所以我們要判斷字串型態是否為ABA 並查找是否有B

2. 開始實作:

a.AB斷點:

       
 s="abyyyab"
        for(int l=1;2*l<s.size();l++){
            string A=s.substr(0,l),maybe_A=s.substr(s.size()-l);
            if(A!=maybe_A)continue;//沒找到的話，就不用做下面的事情
            //......
        }

我們要先看A的長度有多長，使用for迴圈一個一個測試長度
所以迴圈會像是:

如果找到了，就進行下一步

b.找B:

string B=s.substr(l,s.size()-(2*l));
if(binary_search(全部的籤.begin(),全部的籤.end(),B)ans++;

B是字串s中間的那段，去頭(A)去尾(maybe_A)->"yyy"
所以現在的字串s被分為三部分:
ab | yyy | ab
A B A
我們現在要在其他字串中，找到和B一樣的
我們用binary_search 找(先不管binary_search的原理) 如果找到 則ans+1

c.完整程式碼:
!!非常感謝 Bangye Wu無私教授解題思路!!

#include <bits/stdc++.h>
using namespace std;
int m, ans=0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m;
    vector<string> all_string;//全部的籤都存在這邊
    string input;
    for (int i = 0; i < m; i++){//讀取輸入的籤
        cin >> input;
        all_string.push_back(input);
    }
    sort(all_string.begin(),all_string.end());//根據首字母排序 如果首字母一樣，就比對第二個
    for (int i = 0; i < m; i++){
        string s=all_string[i];
        for(int l=1; l*2<s.size(); l++){
            string A=s.substr(0,l),maybe_A=s.substr(s.size()-l);
            if(A!=maybe_A)continue;
            string B=s.substr(l, s.size()-(2*l));
            if(binary_search(all_string.begin(),all_string.end(),B)){
                ans++;
            }
        }
    }
    cout << ans << endl;
}

AC!!