結果

問題 No.430 文字列検索
コンテスト
ユーザー yuji9511
提出日時 2019-09-17 00:33:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 3,098 bytes
コンパイル時間 1,228 ms
コンパイル使用メモリ 165,796 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-10 00:32:28
合計ジャッジ時間 2,130 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i==n-1];};
struct SuffixArray {
    private:
        string S;
        ll N, K;
        ll rank[50010];
        ll tmp[50010];
        ll sa[50010];

    public:
        SuffixArray(){
        }
        void init(string s){
            S = s;
            N = s.size();
            fill(rank, rank+N+1, 0);
            fill(tmp, tmp+N+1, 0);
            fill(sa, sa+N+1, 0);
            rep(i,0,N+1){
                sa[i] = i;
                rank[i] = i < N ? S[i] : -1;
            }
            for(K = 1; K <= N; K *= 2){
                sort(sa, sa+N+1, [&](const ll i, const ll j){
                    if(rank[i] != rank[j]) return rank[i] < rank[j];
                    else{
                        ll ri = i + K <= N ? rank[i+K] : -1;
                        ll rj = j + K <= N ? rank[j+K] : -1;
                        return ri < rj;
                    }
                });

                tmp[sa[0]] = 0;
                rep(i,1,N+1){
                    tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
                }
                rep(i,0,N+1) rank[i] = tmp[i];
            }
        }

        bool compare_sa(const ll i, const ll j){
            if(rank[i] != rank[j]) return rank[i] < rank[j];
            else{
                ll ri = i + K <= N ? rank[i+K] : -1;
                ll rj = j + K <= N ? rank[j+K] : -1;
                return ri < rj;
            }
        }

        ll get(ll n){
            if(n > N){
                return 0;
            }else{
                return rank[n];
            }
        };
} sa;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    ll M;
    cin >> M;
    string C[5010];
    rep(i,0,M) cin >> C[i];
    sa.init(S);
    ll N = S.size();
    ll st[50010];
    rep(i,0,N){
        st[sa.get(i)-1] = i;
    }
    ll ans = 0;
    rep(i,0,M){
        ll lv = -1, rv = N-1;
        while(rv - lv > 1){
            ll mid = (rv + lv) / 2;
            if(C[i] > S.substr(st[mid], C[i].size())){
                lv = mid;
            }else{
                rv = mid;
            }
        }
        ll idx = rv;
        while(idx < N){
            if(C[i] == S.substr(st[idx], C[i].size())){
                ans++;
                idx++;
            }else{
                break;
            }
        }
    }
    print(ans);


    // ll ans = 0;
    // ll N = S.size();
    // RollingHash rh(S);
    // rep(i,0,M){
    //     RollingHash rh2(C[i]);
    //     ll sz = C[i].size();
    //     rep(j,0,N){
    //         if(rh.get(j, j+sz) == rh2.get(0,sz)){
    //             ans++;
    //         }
    //     }
    // }
    // print(ans);
}
0