結果

問題 No.430 文字列検索
コンテスト
ユーザー Bantako
提出日時 2018-12-29 19:51:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,544 bytes
コンパイル時間 1,793 ms
コンパイル使用メモリ 170,764 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-10 00:21:03
合計ジャッジ時間 5,129 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
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