#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef DEBUG #include "./Lib/debug.hpp" #else #define dump(...) templateinline 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; using VS = std::vector; using VL = std::vector; using VVL = std::vector; using VVVL = std::vector; using VD = std::vector; template using V = std::vector; /* 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> { public: size_t operator()(const std::pair& x) const { return hash()(1000000000 * x.first + x.second); } }; } /* input */ template std::istream& operator >> (std::istream& is, vector& 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 m_suffixArray; /* string to vector */ static std::vector toIntVec(const std::string& str) { std::vector 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 classifying(const std::vector& str) { auto sz = str.size(); auto typeArray = std::vector(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 inducedSort(const std::vector& str, const std::vector& type, std::list& lmsList) { auto sz = str.size(); auto nList = std::set(); 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>(); for (const auto& i : lmsList) { tailList[str[i]].emplace_back(i); } /* set L-type */ auto headList = std::unordered_map>(); for (const auto& n : nList) { checkAndUpdate(n, headList, headList, false); checkAndUpdate(n, tailList, headList, false); } /* set S-type*/ tailList = std::unordered_map>(); 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(); 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 getLmsChanger(const std::vector& str, const std::vector& type, const std::list& lms) { if (lms.size() == 1) { return std::unordered_map{ { str.size() - 1, 0 }}; } std::unordered_map changer{{static_cast(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 constructSuffixArray(const std::vector& str) { auto type = classifying(str); /* calc fake Suffix Array using order seed*/ auto lmsOrder = [&type]() { auto lms = std::list(); 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(); lms.emplace_back(static_cast(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(); auto def = std::vector(); 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{static_cast(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 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 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; }