ZeroJudge H083: Digital Divination

The fortune-telling tube contains M sticks, each stick is a string composed of lowercase English letters. Two sticks are drawn from the tube. If concatenating the strings S and T from these two sticks forms a string that can be split into two halves with the same content, then drawing the divine lot means the gods agree; otherwise, it means the gods disagree or have no response.

For example, if the strings on the two drawn sticks are "piep" and "ie", then the concatenated string "piepie" can be split into two halves with the same content "pie" and "pie", which satisfies the condition. However, if the two drawn sticks are "foo" and "bar", the condition is not satisfied.

Interestingly, if the two drawn sticks S and T are considered a divine lot, then regardless of whether T is appended to S or the order is reversed, it will still be considered a divine lot. This further illustrates the mysterious power blessing the fortunate ones who draw these sticks.

For example, "piep" and "ie" can be concatenated as "piepie" or "iepiep", both of which can be split into two identical substrings.

To determine how many pairs of sticks in the tube can form a valid fortune-telling result, counting each pair of identical sticks once is sufficient.

Sample Inputs/Outputs

Thought Process

When receiving strings, use a Map or Set to store which strings have appeared. Then, iterate through each string one by one. Using a for loop from 0 to half the length of the string plus 1 (because we need to substring), check if the first i characters of the string are equal to the last i characters of the string. If they are equal, check if the middle character exists in the input. If it does, increment the answer by 1. Finally, output the answer. If there are too many substring operations, it might lead to TLE, so it's important to optimize to avoid excessive substring operations.

Sample Code－ZeroJudge H083: Digital Divination

#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