結果

問題 No.1018 suffixsuffixsuffix
ユーザー mtsd
提出日時 2020-04-03 22:48:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 346 ms / 2,000 ms
コード長 5,421 bytes
コンパイル時間 1,653 ms
コンパイル使用メモリ 137,404 KB
実行使用メモリ 15,784 KB
最終ジャッジ日時 2024-07-03 05:16:04
合計ジャッジ時間 10,962 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}

class KMP
{
public:
    string pattern;
    int plen;
    vector<int> table;
    KMP(const string& s) : pattern(s), plen((int)pattern.size()), table(plen + 1){
        table[0] = -1;
        int j = -1;
        for(int i = 0; i < plen; ++i){
            while(j >= 0 && pattern[i] != pattern[j]){
                j = table[j];
            }
            table[i+1] = ++j;
        }
    }
    void search(const string& text, vector<int>& res){
        int head = 0, j = 0, tlen = (int)text.size();
        while(head + j < tlen){
            if(pattern[j] == text[head + j]) {
                if(++j == plen){
                    res.push_back(head);
                    head = head + j - table[j];
                    j = table[j];
                }
            }else{
                head = head + j - table[j];
                if(j) j = table[j];
            }
        }
    }
};
 
// 文字列 s[0, i] の最小周期の長さ
void minimum_cycle(const string& s, vector<int>& res){
	KMP kmp(s);
	res.resize((int)s.size());
	for(int i = 0; i < (int)s.size(); ++i){
		res[i] = i + 1 - kmp.table[i+1];
	}
}
class suffixarray{
public:
    int sz,index1,index2;
    vector<int> rnk,tmp,sa,lcp;
    string recs;
    suffixarray(string s){
        recs = s;
        sz = (int)s.size();
        rnk.resize(sz+1),tmp.resize(sz+1);
        make_sa();
        // make_lcp();
    }
    void make_sa(){
        index1 = sz;
        sa.resize(index1+1);
        for(int i = 0; i < index1+1; i++){
            sa[i] = i;
            rnk[i] = i<index1?recs[i]:-1;
        }
        auto comp = [&](int i,int j){
            if(rnk[i] != rnk[j]){
                return rnk[i] < rnk[j];
            }else{
                int ri = (i+index2<=index1)?rnk[i+index2]:-1;
                int rj = (j+index2<=index1)?rnk[j+index2]:-1;
                return ri < rj;
            }
        };
        for(index2=1;index2<=index1;index2*=2){
            sort(sa.begin(),sa.end(),comp);
            tmp[sa[0]] = 0;
            for(int i=1;i<=index1;i++){
                tmp[sa[i]] = tmp[sa[i-1]]+(comp(sa[i-1],sa[i])?1:0);
            }
            for(int i = 0; i < index1+1; i++){
                rnk[i] = tmp[i];
            }
        }
    }
    void make_lcp(){
        lcp.resize(sz+1);
        for(int i = 0; i < sz+1; i++){
            rnk[sa[i]] = i;
        }
        int h = 0;
        lcp[0] = 0;
        for(int i = 0; i < sz; i++){
            int j = sa[rnk[i]-1];
            if(h > 0){
                h--;
            }
            for(;j+h<sz&&i+h<sz;h++){
                if(recs[j+h] != recs[i+h]){
                    break;
                }
            }
            lcp[rnk[i]-1] = h;
        }
    }
};

int main(){
    ll n,m,q;
    cin >> n >> m >> q;
    string s;
    cin >> s;
    
    if(m==1){    
        suffixarray sss(s);
        vector<int> sa = sss.sa;
        rep(i,q){
            int k;
            cin >> k;
            cout << sa[k]+1 << " ";
        }
        cout << endl;
        return 0;
    }

    vector<int> res;
    minimum_cycle(s,res);
    ll c = res[n-1];
    // cerr << c << endl;
    if(n%c!=0)c = n;
    ll loop = n*m/c;
    string t;
    rep(i,c){
        t.push_back(s[i]);
    }
    s = t;
    s += s;
    suffixarray sss(s);
    vector<int> sa = sss.sa;
    set<int> st;
    set<int> sst;
    
    vector<pair<ll,pair<bool,ll> > > a;
    for(int i=1;i<=s.size();i++){
        if(sa[i]>=c){
            a.push_back(MP(sa[i]%c,MP(1,1)));
        }else{
            a.push_back(MP(sa[i]%c,MP(0,loop-1)));
        }
    }
    // for(auto x:a){
    //     cerr << x.first << " " << x.second.first << " " << x.second.second << endl;
    // }
    // cerr << c << "  "  << loop << endl;
    vector<ll> cnt;
    ll sm = 0;
    for(auto x:a){
        cnt.push_back(sm);
        sm += x.second.second;
    }
    rep(i,q){
        ll k;
        cin >> k;
        int id = lower_bound(all(cnt),k)-cnt.begin() -1;
        ll res = 0;
        ll D = k - cnt[id];
        if(a[id].second.first){
            res = c*(loop-1) + a[id].first;
        }else if(a[id].second.second==loop){
            res = c*(loop-1) + a[id].first;
            res -= c*(D-1);
        }else{
            res = c*(loop-2) + a[id].first;
            res -= c*(D-1);
        }
        cout << res+1 << " ";
        
    }
    cout << "\n";
    return 0;
}
0