結果

問題 No.430 文字列検索
ユーザー BantakoBantako
提出日時 2018-12-29 19:51:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,544 bytes
コンパイル時間 1,780 ms
コンパイル使用メモリ 168,348 KB
実行使用メモリ 13,752 KB
最終ジャッジ日時 2024-04-09 21:13:25
合計ジャッジ時間 5,306 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,752 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
bool charsearch(string s,char c){
    rep(i, 0, s.length()){
        if(s[i] != c)return 1;
    }
    return 0;
}
main(){
    	cin.tie(0);
   	ios::sync_with_stdio(false);
    string S;
    cin >> S;
    vector<int> reptable[26];
    int pre = 0;
    rep(i,1,S.size()){
        if(S[i-1] != S[i]){
            reptable[S[i-1] - 'A'].push_back(i - pre);
            pre = i;
        }
    }
    reptable[S.back() - 'A'].push_back(S.size() - pre);
    int M;
    cin >> M;
    ll cnt = 0;
    int table[10] = {};
    rep(i,0,M){
        string T;
        cin >> T;
        if(charsearch(T, T[0])){
            int j = 0;
            rep(k,0,T.size()){
                if(T[k] == T[j]){
                    table[k] = j++;
                }else{
                    table[k] = j;
                    j = 0;
                }
            }
            int p = 0;
            rep(j,0,S.size()){
                if(S[j] == T[p]){
                    p++;
                }else if(p == 0){

                }else{
                    p = table[p];
                    j--;
                }
                if(p == T.size()){
                    cnt++;
                    p = 0;
                }

            }
        }else{
            for(int num:reptable[T[0] - 'A']){
                cnt += max(0, (int)(num - T.size() + 1) );
            }
        }
    }
    cout << cnt << endl;
}
0