【題解】Zerojudge h083 - 3. 數位占卜

題目連結

題目大意

給定 $n$ 個字串 $s_1, \dots, s_n$，問有幾組 $(i, j)$ 滿足 $s_i$ 和 $s_j$ 合併後從中間切開左右兩邊為相同的字串 (piep + ie = pie|pie)。$(i, j)$ 和 $(j, i)$ 只會被計算一次。

題解

對於每個 $s_i$，我們把它當作是比較長的那個字串，則枚舉比較短的那個字串缺少的前綴長度 $len$，則首先必須滿足 $s_i[0, len - 1] = s_i[|s_i| - len, |s_i| - 1]$，也就是前綴相同。如果前綴相同，則因為從中間切開左右兩邊字串相同，$s_j = s_i[len, |s_i| - 2 \cdot len]$。我們可以用 std::set 來維護出現哪些字串。其他實作的細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<string> S(n);
	set<string> all;
	for(int i = 0; i < n; i++) {
		cin >> S[i];
		all.insert(S[i]);
	}
	long long ans = 0;
	for(auto s : S) {
		for(int len = 1; len * 2 < (int) s.size(); len++) {
			string head = s.substr(0, len);
			string tail = s.substr(s.size() - len, len);
			if(head == tail) {
				string want = s.substr(len, s.size() - len * 2);
				ans += all.count(want);
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge h083 - 3. 數位占卜