#42968: C++查找字串注意事項
jamil130011@gmail.com
(許恩嘉)
學校
:
不指定學校
編號 : 249076
來源 : [114.47.150.56]
最後登入時間 ：
2025-08-10 16:54:10
unordered_set比set快，不過在使用unordered_set時，建議預先設置較大的桶的數量，以減少重新哈希（Rehashing）的開銷。當僅差臨門一腳時可以試試。(當然更好的做法是檢查你的演算法是哪裡寫差了，好的演算法不用這麼做也能通過)。
桶的數量可以在建構unordered_set時給出:
std::unordered_set<string> A(50000);
也可以使用.reserve()
A.reserve(50000);
解題思路:
1.將所有字串存進unordered_set
2.迭代所有字串，檢查其前i個字元與後i個字元是否相等，如果相等，則檢查unordered_set中是否有包含(去掉前i個字元與後i個字元後剩下的子字串)。i=1~(字串長度+1)/2
#include<iostream>
#include<string>
#include<cstring>
#include<unordered_set>
#include<vector>
using std::cin;
using std::string;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> m;
std::vector<string> s(m);
for (auto& i : s) {
cin >> i;
}
std::unordered_set<string> B;
for (auto& i : s) {
B.emplace(i);
}
int count = 0;
for (auto& i : s) {
int half = (i.size() + 1) / 2;
const char* p = i.data();
int len = i.length();
for (int j = 1; j < half; ++j) {
if (!memcmp(p, p + len - j, j)) {//直接用memcmp進行比較而不是生成substr再比較以減少生成子字串的開銷
count += B.count(i.substr(j, len - j * 2));
}
}
}
std::cout << count;
}
#42969: Re: C++查找字串注意事項
jamil130011@gmail.com
(許恩嘉)
學校
:
不指定學校
編號 : 249076
來源 : [114.47.150.56]
最後登入時間 ：
2025-08-10 16:54:10
std::unordered_set<string> B;
應為
std::unordered_set<string> B(m*2);
我剛剛為了測試預先設置桶數量與未預先設置桶數量之間的性能差異而刪去的內容忘記加回來了啊啊啊
是說到底為什麼這網站沒有「編輯已發布的內容」的功能啊!