#42968: C++查找字串注意事項
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++查找字串注意事項
ZeroJudge Forum