#include #include #include using namespace std; vector x; vector> childrenId; int ptr; void init() { constexpr int N = 50'005; x.assign(N, 0); childrenId.assign(26, vector(N, -1)); ptr = 0; } void insert(int id, const string &s) { for(char c : s) { int pos = c - 'A'; int &childId = childrenId[pos][id]; if(childId == -1) { childId = ++ptr; } id = childId; } ++x[id]; } int count(int id, const string &s) { int res = 0; for(char c : s) { int pos = c - 'A'; int &childId = childrenId[pos][id]; if(childId == -1) { break; } res += x[childId]; id = childId; } return res; } int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); string s; cin >> s; int M; cin >> M; init(); for(int i=0; i> ci; insert(0, ci); } int res = 0; for(size_t i=0, n=s.size(); i