結果

問題 No.430 文字列検索
ユーザー @abcde@abcde
提出日時 2019-06-06 23:36:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 283 ms / 2,000 ms
コード長 3,475 bytes
コンパイル時間 1,928 ms
コンパイル使用メモリ 179,592 KB
実行使用メモリ 35,968 KB
最終ジャッジ日時 2024-11-10 00:25:54
合計ジャッジ時間 3,670 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 283 ms
35,968 KB
testcase_02 AC 16 ms
5,248 KB
testcase_03 AC 17 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 281 ms
35,840 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 19 ms
6,656 KB
testcase_11 AC 103 ms
11,008 KB
testcase_12 AC 102 ms
10,880 KB
testcase_13 AC 102 ms
11,008 KB
testcase_14 AC 77 ms
7,552 KB
testcase_15 AC 61 ms
5,888 KB
testcase_16 AC 26 ms
5,248 KB
testcase_17 AC 21 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// TLE版.
// #include <bits/stdc++.h>
// using namespace std;
// 
// int main() {
//     
//     // 1. 入力情報取得.
//     string S;
//     int M;
//     cin >> S >> M;
//     
//     // 2. 文字列S について, i文字目 の アルファベット情報(位置) を 保存
//     const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//     vector<vector<int>> 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 <bits/stdc++.h>
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<map<string, int>> vm;
    for(int i = 0; i < 10; i++){
        map<string, int> 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;
    
}
0