結果
問題 | No.430 文字列検索 |
ユーザー | cutmdo |
提出日時 | 2019-08-21 05:29:26 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 9,342 bytes |
コンパイル時間 | 2,157 ms |
コンパイル使用メモリ | 155,200 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-11-10 00:29:01 |
合計ジャッジ時間 | 4,177 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 187 ms
9,856 KB |
testcase_02 | AC | 242 ms
6,272 KB |
testcase_03 | AC | 60 ms
8,964 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 59 ms
9,728 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 7 ms
5,248 KB |
testcase_11 | AC | 166 ms
7,680 KB |
testcase_12 | AC | 166 ms
7,680 KB |
testcase_13 | AC | 178 ms
7,808 KB |
testcase_14 | AC | 211 ms
7,508 KB |
testcase_15 | AC | 168 ms
7,448 KB |
testcase_16 | AC | 140 ms
6,400 KB |
testcase_17 | AC | 154 ms
6,272 KB |
ソースコード
#include <iostream> #include <iomanip> #include <string> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <list> #include <stack> #include <queue> #include <bitset> #include <numeric> #include <cassert> #ifdef DEBUG #include "./Lib/debug.hpp" #else #define dump(...) template<class T>inline auto d_val(T a, T b) { return a; } #endif /* (=^o^=) */ #define int ll /* macro */ #define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i) #define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) RFOR(i, 0, n) #define REPC(x,c) for(const auto& x:(c)) #define REPI2(it,b,e) for(auto it = (b); it != (e); ++it) #define REPI(it,c) REPI2(it, (c).begin(), (c).end()) #define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend()) #define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);) #define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end()) #define ALL(x) (x).begin(),(x).end() #define cauto const auto& /* macro func */ #define SORT(x) do{sort(ALL(x));}while(false) #define RSORT(x) do{sort((x).rbegin(),(x).rend());}while(false) #define UNIQUE(v) do{v.erase( unique(v.begin(), v.end()), v.end() );}while(false) #define MAX(x,y) do{x = std::max(x,y);}while(false) #define MIN(x,y) do{x = std::min(x,y);}while(false) #define BR do{cout<<"\n";}while(false) /* type define */ using ll = long long; using PAIR = std::pair<ll, ll>; using VS = std::vector<std::string>; using VL = std::vector<long long>; using VVL = std::vector<VL>; using VVVL = std::vector<VVL>; using VD = std::vector<double>; template<class T> using V = std::vector<T>; /* using std */ using std::cout; constexpr char endl = '\n'; using std::cin; using std::sort; using std::pair; using std::string; using std::stack; using std::queue; using std::vector; using std::list; using std::map; using std::unordered_map; using std::multimap; using std::unordered_multimap; using std::set; using std::unordered_set; using std::unordered_multiset; using std::multiset; using std::bitset; using std::priority_queue; /* constant value */ constexpr ll MOD = 1000000007; //constexpr ll MOD = 998244353; /* Initial processing */ struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing; /* Remove the source of the bug */ signed pow(signed, signed) { assert(false); return -1; } /* define hash */ namespace std { template <> class hash<std::pair<ll, ll>> { public: size_t operator()(const std::pair<ll, ll>& x) const { return hash<ll>()(1000000000 * x.first + x.second); } }; } /* input */ template<class T> std::istream& operator >> (std::istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; } //============================================================================================= /** * SuffixArrayを構築する * O(N) * 文字列の全てのsuffixをソートした配列が得られる * ex) abadc -> [0, 2, 1, 4, 3]([abadc, adc, badc, c, dc]) * * SA-IS(Suffix Array - Induced Sort)で実装 */ class SuffixArray { enum class TYPE { L, S, LMS }; const std::string m_str; const std::vector<int> m_suffixArray; /* string to vector<int> */ static std::vector<int> toIntVec(const std::string& str) { std::vector<int> vec; vec.reserve(str.size() + 1); for (const auto& c : str) { vec.emplace_back(c - '0' + 1); } vec.emplace_back(0); return vec; } /* classify { L, S, LMS } */ static std::vector<TYPE> classifying(const std::vector<int>& str) { auto sz = str.size(); auto typeArray = std::vector<TYPE>(sz); typeArray[sz - 1] = TYPE::S; for (int i = sz - 2; i >= 0; --i) { if (str[i] == str[i + 1]) { typeArray[i] = typeArray[i + 1]; continue; } typeArray[i] = (str[i] < str[i + 1]) ? TYPE::S : TYPE::L; } for (int i = 1; i < sz; ++i) { if (typeArray[i - 1] == TYPE::L && typeArray[i] == TYPE::S) { typeArray[i] = TYPE::LMS; } } return typeArray; } /* induced sort */ static std::vector<int> inducedSort(const std::vector<int>& str, const std::vector<TYPE>& type, std::list<int>& lmsList) { auto sz = str.size(); auto nList = std::set<int>(); for (const auto& c : str) { nList.emplace(c); } auto befCheck = [&](int k, auto& addList, bool rev) { if (k == 0) { return; } if (!rev && type[k - 1] == TYPE::L) { addList[str[k - 1]].emplace_back(k - 1); } if (rev && type[k - 1] != TYPE::L) { addList[str[k - 1]].emplace_front(k - 1); } }; auto checkAndUpdate = [&](int n, auto& checkList, auto& addList, bool rev) { auto& lst = checkList[n]; if (rev) { for (auto itr = lst.rbegin(); itr != lst.rend(); ++itr) { befCheck(*itr, addList, rev); } } else { for (const auto& k : lst) { befCheck(k, addList, rev); } } }; /* set LMS */ auto tailList = std::unordered_map<int, std::list<int>>(); for (const auto& i : lmsList) { tailList[str[i]].emplace_back(i); } /* set L-type */ auto headList = std::unordered_map<int, std::list<int>>(); for (const auto& n : nList) { checkAndUpdate(n, headList, headList, false); checkAndUpdate(n, tailList, headList, false); } /* set S-type*/ tailList = std::unordered_map<int, std::list<int>>(); for (auto itr_n = nList.rbegin(); itr_n != nList.rend(); ++itr_n) { auto n = *itr_n; checkAndUpdate(n, tailList, tailList, true); checkAndUpdate(n, headList, tailList, true); } /* merge */ auto suffixArray = std::vector<int>(); suffixArray.reserve(sz); for (const auto& n : nList) { for (const auto& c : headList[n]) { suffixArray.emplace_back(c); } for (const auto& c : tailList[n]) { suffixArray.emplace_back(c); } } return suffixArray; } /* order lms -> sorted lms */ static std::unordered_map<int, int> getLmsChanger(const std::vector<int>& str, const std::vector<TYPE>& type, const std::list<int>& lms) { if (lms.size() == 1) { return std::unordered_map<int, int>{ { str.size() - 1, 0 }}; } std::unordered_map<int, int> changer{{static_cast<int>(str.size()) - 1,0},{*++lms.begin(),1}}; int num = 1; for (auto itr = ++lms.begin(); itr != (--lms.end());) { auto f1 = *itr; auto f2 = *(++itr); bool isSame = false; for (int i = 0;; ++i) { if (str[f1 + i] != str[f2 + i]) { break; } auto b1 = (type[f1 + i] == TYPE::LMS); auto b2 = (type[f2 + i] == TYPE::LMS); if (b1 | b2 && i > 0) { if (b1 & b2) { isSame = true; break; } break; } } if (!isSame) { ++num; } changer.emplace(f2, num); } return changer; } /* calc Suffix Array*/ static std::vector<int> constructSuffixArray(const std::vector<int>& str) { auto type = classifying(str); /* calc fake Suffix Array using order seed*/ auto lmsOrder = [&type]() { auto lms = std::list<int>(); for (int i = 0; i < type.size(); ++i) if (type[i] == TYPE::LMS) { lms.emplace_back(i); } return lms; }(); auto fakeArray = inducedSort(str, type, lmsOrder); /* calc true seed */ auto lmsFakeOrder = [&fakeArray, &type]() { auto lms = std::list<int>(); lms.emplace_back(static_cast<int>(type.size()) - 1); for (const auto& i : fakeArray) if (type[i] == TYPE::LMS) { lms.emplace_back(i); } return lms; }(); auto changer = getLmsChanger(str, type, lmsFakeOrder); auto& lmsTrueOrder = lmsFakeOrder; if (changer[*lmsFakeOrder.rbegin()] + 1 < lmsFakeOrder.size()) { /* exist same lms-substring */ auto str = std::vector<int>(); auto def = std::vector<int>(); str.reserve(lmsOrder.size()); def.reserve(lmsOrder.size()); for (const auto& c : lmsOrder) { str.emplace_back(changer[c]); def.emplace_back(c); } auto lmsSuffixArray = constructSuffixArray(str); lmsTrueOrder = std::list<int>{static_cast<int>(type.size()) - 1}; for (const auto& c : lmsSuffixArray) { lmsTrueOrder.emplace_back(def[c]); } } /* calc true Suffix Array using true seed */ auto suffixArray = inducedSort(str, type, lmsTrueOrder); return suffixArray; } public: SuffixArray(const std::string& str) :m_str(str), m_suffixArray(constructSuffixArray(toIntVec(str))) {} /** * 引数として与えられたpatternの出現位置リストを返す */ std::list<int> findPattern(const std::string& pattern) const { auto find = [&](const std::string& ptn) { int end = m_suffixArray.size(); int ok = end; int ng = -1; while (ok - ng > 1) { int mid = (ok + ng) / 2; auto sub = m_str.substr(m_suffixArray[mid], end); int isOk = (ptn <= sub); if (isOk) { ok = mid; } else { ng = mid; } } return ok; }; auto patternUpper = [&pattern]() { auto ptn = pattern; ++* ptn.rbegin(); return ptn; }(); auto fl = find(pattern); auto fu = find(patternUpper); std::list<int> lst; for (int i = fl; i < fu; ++i) { lst.emplace_back(m_suffixArray[i]); } return lst; } auto getSuffixArray() const { return m_suffixArray; } /* output fot debug */ void debugOutput() const { dump(m_suffixArray); auto end = m_str.size(); REPC(x, m_suffixArray) { cout << m_str.substr(x, end) << endl; } } }; signed main() { string str; cin >> str; ll q; cin >> q; auto sa = SuffixArray(str); ll ans = 0; REP(_, q) { string p; cin >> p; ans += sa.findPattern(p).size(); } cout << ans << endl; }