// TLE版. // #include // using namespace std; // // int main() { // // // 1. 入力情報取得. // string S; // int M; // cin >> S >> M; // // // 2. 文字列S について, i文字目 の アルファベット情報(位置) を 保存 // const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // vector> pos(26); // for(int i = 0; i < S.size(); i++) pos[S[i] - 'A'].push_back(i); // // for(auto &v : pos){ // // for(auto &p : v) cout << p << " "; // // cout << endl; // // } // // // 3. すべての部分文字列の数をカウント. // int ans = 0; // for(int i = 0; i < M; i++){ // string C; // cin >> C; // // 先頭文字 に 対応するインデックスを取得. // int index = C[0] - 'A'; // int l = C.size(); // // 文字列S の 部分文字列 と 比較して, 等しい場合は, インクリメント. // for(auto &v : pos[index]) if(C == S.substr(v, l)) ans++; // } // // // 4. 後処理. // cout << ans << endl; // return 0; // // } // // TODO: 高速化. #include using namespace std; int main() { // 1. 入力情報取得. string S; int M; cin >> S >> M; S += "##########"; // 番兵追加. // 2. 文字列S について, 1 ~ 10文字ずつ分割して, 各文字列ごとに, 出現回数を保存. // ex // [入力例] // ABCBCBA // 3 // A // BC // ABC // // [出力例] // # 10 // A 2 // B 3 // C 2 // ## 9 // A# 1 // AB 1 // BA 1 // BC 2 // CB 2 // ### 8 // A## 1 // ABC 1 // BA# 1 // BCB 2 // CBA 1 // CBC 1 // #### 7 // A### 1 // ABCB 1 // BA## 1 // BCBA 1 // BCBC 1 // CBA# 1 // CBCB 1 // ##### 6 // A#### 1 // ABCBC 1 // BA### 1 // BCBA# 1 // BCBCB 1 // CBA## 1 // CBCBA 1 // ###### 5 // A##### 1 // ABCBCB 1 // BA#### 1 // BCBA## 1 // BCBCBA 1 // CBA### 1 // CBCBA# 1 // ####### 4 // A###### 1 // ABCBCBA 1 // BA##### 1 // BCBA### 1 // BCBCBA# 1 // CBA#### 1 // CBCBA## 1 // ######## 3 // A####### 1 // ABCBCBA# 1 // BA###### 1 // BCBA#### 1 // BCBCBA## 1 // CBA##### 1 // CBCBA### 1 // ######### 2 // A######## 1 // ABCBCBA## 1 // BA####### 1 // BCBA##### 1 // BCBCBA### 1 // CBA###### 1 // CBCBA#### 1 // ########## 1 // A######### 1 // ABCBCBA### 1 // BA######## 1 // BCBA###### 1 // BCBCBA#### 1 // CBA####### 1 // CBCBA##### 1 // -> ここでは, 5回 のはず. vector> vm; for(int i = 0; i < 10; i++){ map m; for(int j = 0; j < S.size() - i; j++){ string s = S.substr(j, i + 1); m[s]++; } vm.push_back(m); } // for(auto &v : vm) for(auto &p : v) cout << p.first << " " << p.second << endl; // 3. すべての部分文字列を数え上げる. int ans = 0; for(int i = 0; i < M; i++){ string C; cin >> C; // 文字列C の 長さに等しい map で, 個数 を カウントアップ int l = C.size(); ans += vm[l - 1][C]; } // 4. 後処理. cout << ans << endl; return 0; }