#690701 (C++14) No.430 文字列検索

提出ソース

結果

問題	No.430 文字列検索
ユーザー	suta28407928
提出日時	2021-08-18 18:09:24
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	14 ms / 2,000 ms
コード長	7,751 bytes
コンパイル時間	2,626 ms
コンパイル使用メモリ	200,192 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-10 00:57:18
合計ジャッジ時間	3,307 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	12 ms 6,816 KB
testcase_02	AC	8 ms 6,820 KB
testcase_03	AC	9 ms 6,820 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	7 ms 6,820 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	13 ms 6,816 KB
testcase_12	AC	13 ms 6,816 KB
testcase_13	AC	14 ms 6,816 KB
testcase_14	AC	13 ms 6,816 KB
testcase_15	AC	12 ms 6,816 KB
testcase_16	AC	9 ms 6,820 KB
testcase_17	AC	9 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define DEBUG
#ifdef DEBUG
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '{';
    for(int i = 0; i < (int)v.size(); i++) {
        if(i) { os << ','; }
        os << v[i];
    }
    os << '}';
    return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &... args) {
    cerr << " " << x;
    debugg(args...);
}
#define debug(...)                                                             \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]: ", debugg(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = (1<<30)-1;
const ll linf = 1LL<<61;
const int MAX = 510000;
int dy[8] = {0,1,0,-1,1,-1,-1,1};
int dx[8] = {-1,0,1,0,1,-1,1,-1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    int sz = a.size();
    for(auto itr = a.begin(); itr != a.end(); itr++){
		cout << *itr;
        sz--;
        if(sz) cout << " ";
	}
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){
	cout << a << " " << b << "\n";
}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
void mark() {cout << "#" << "\n";}
ll pcount(ll x) {return __builtin_popcountll(x);}
const int mod = 1e9 + 7;
//const int mod = 998244353;

struct SA_IS{
    std::vector<int> sa;
    std::vector<int> lcp;

    SA_IS(std::string str){
        str += '$';
        int n = str.size();
        std::vector<int> s(n);
        for(int i=0; i<n; i++) s[i] = str[i] - '$';
        sa = sa_is(s, 100);
        lcp.resize(n);
        make_lcp(str);
    }

    SA_IS(vector<int> str, int k){
        str.push_back(0);
        int n = str.size();
        sa = sa_is(str, k);
    }

    void induced_sort(std::vector<int> &sa, std::vector<int> &s, std::vector<int> &lms, std::string &ls, int k){
        int n = s.size();
        std::vector<int> c_size(k,0), bin(k+1,0), count(k,0);
        for(int i=0; i<n; i++){
            c_size[s[i]]++;
        }
        for(int i=0; i<k; i++){
            bin[i+1] = bin[i] + c_size[i];
        }

        for(int i=lms.size()-1; i>=0; i--){
            int id = s[lms[i]];
            sa[bin[id+1] - 1 - count[id]] = lms[i];
            count[id]++;
        }
        
        //L-sort
        std::fill(count.begin(), count.end(), 0);
        for(int i=0; i<n; i++){
            if(sa[i] == -1) continue;
            int next = sa[i] - 1;
            if(next == -1 || ls[next] == 'S') continue;
            int id = s[next];
            sa[bin[id] + count[id]] = next;
            count[id]++;
            if(i > 0 && ls[sa[i]] == 'S' && ls[sa[i]-1] == 'L') sa[i] = -1;
        }

        //S-sort
        std::fill(count.begin(), count.end(), 0);
        for(int i=n-1; i>=0; i--){
            if(sa[i] == -1) continue;
            int next = sa[i] - 1;
            if(next == -1 || ls[next] == 'L') continue;
            int id = s[next];
            sa[bin[id+1] - 1 - count[id]] = next;
            count[id]++;
        }
    }

    std::vector<int> sa_is(std::vector<int> &s, int k){
        int n = s.size();
        std::vector<int> sa(n,-1);
        std::vector<bool> is_lms(n,false);
        std::string ls;
        ls.resize(n);
        ls[n-1] = 'S';
        for(int i=n-2; i>=0; i--){
            if(s[i] < s[i+1]) ls[i] = 'S';
            else if(s[i] > s[i+1]) ls[i] = 'L';
            else ls[i] = ls[i+1];
        }
        std::vector<int> lms, sorted_lms;
        for(int i=0; i<n-1; i++){
            if(ls[i] == 'L' && ls[i+1] == 'S'){
                lms.push_back(i+1);
                is_lms[i+1] = true;
            }
        }
        
        //1回目のinduced_sortでlms-substringが辞書順にソートされる
        induced_sort(sa,s,lms,ls,k);

        for(int i=0; i<n; i++){
            if(is_lms[sa[i]]){
                sorted_lms.push_back(sa[i]);
            }
            sa[i] = -1;
        }

        sa[sorted_lms[0]] = 0;
        int kind = 0;
        for(int i=0; i<sorted_lms.size()-1; i++){
            bool same = true;
            int x = sorted_lms[i];
            int y = sorted_lms[i+1];
            int d = 0;
            while(1){
                if(x+d == n || y+d == n){
                    if(x+d == n){
                        if(!is_lms[y+d]) same = false; 
                    }else{
                        if(!is_lms[x+d]) same = false;
                    }
                    break;
                }
                if(d > 0 && (is_lms[x+d] || is_lms[y+d])){
                    if(is_lms[x+d] != is_lms[y+d]) same = false;
                    break;
                }
                if(s[x+d] != s[y+d]){
                    same = false;
                    break;
                }
                d++;
            }
            if(!same) kind++;
            sa[sorted_lms[i+1]] = kind;
        }

        std::vector<int> new_str;
        for(int i=0; i<n; i++){
            if(is_lms[i]){
                new_str.push_back(sa[i]);
                sa[i] = -1;
            }
        }

        vector<int> new_lms(lms.size());
        if(kind + 1 == lms.size()){
            new_lms = sorted_lms;
        }else{
            sorted_lms = sa_is(new_str, kind + 1);
            for(int i=0; i<sorted_lms.size(); i++){
                new_lms[i] = lms[sorted_lms[i]];
            }
        }
        
        induced_sort(sa,s,new_lms,ls,k);
        return sa;
    }

    void make_lcp(string &s){
        s.pop_back();
        int n = s.size();
        vector<int> ran(n+1);
        for(int i=0; i<=n; i++) ran[sa[i]] = i;
        
        int h = 0;
        lcp[0] = 0;
        for(int i=0; i<n; i++){
            int j = sa[ran[i]-1];
            if(h > 0) h--;
            for(; j+h<n && i+h<n; h++){
                if(s[j+h] != s[i+h]) break;
            }
            lcp[ran[i]-1] = h;
        }
    }
};

int main(){
    string s; cin >> s;
    int n = s.size();
    int q; cin >> q;
    SA_IS sa(s);
    ll ans = 0;
    rep(i,q){
        string t; cin >> t;
        int l = 0, r = n+1;
        int m = t.size();
        while(r-l > 1){
            int mi = (r+l)/2;
            int id = sa.sa[mi];
            if(s.substr(id,min(m,n-id)) < t) l = mi;
            else r = mi;
        }
        int L = l;
        l = 0, r = n+1;
        while(r-l > 1){
            int mi = (r+l)/2;
            int id = sa.sa[mi];
            if(s.substr(id,min(m,n-id)) <= t) l = mi;
            else r = mi;
        }
        ans += l-L;
    }
    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード