2016年8月30日 星期二

Codeforces 128B. String

/*
    題目連結

    字串題?! (誤
    我不太擅長字串啊(笑

    看到想拿來練習一下 Suffix Array
    但寫到一半 發現其實自己不會用SA來解這題
    外加 k 小的異常 就決定重新想

    注意到 p 的字典序一定比 p+q 小
    所以 s[i:i] 會比 s[i:i+j] 小
    於是想到一個做法 那就是把所有 s[i:i] push 到 priority_queue (pq) 裡
    每次 pop 出一個 s[i:j] 就把 s[i:j+1] (如果存在)再 push 進去
    那第k個 pop出來得即為答案

    接著來算算複雜度 設字串長為L
    O(k*log(L)*平均字串比大小時間)
    字串比大小時間 最差為L  乍看算出來 > 10^10
    似乎不可行 但考慮到多種情況發現 並不會那麼差
    傳上去 0.1s AC 毫無時間壓力

    另外注意到 
    我並沒有把字串真的丟到 pq裡而是放在外頭
    不然要構造出那些字串 就需要 L^2 的時間
    雖然有人這樣還是過了 OAO
    但我這樣比較快 XD
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

char c[100001];
int cn;

string s[100001];
int ed[100001];

struct Cmp{
    bool operator()(int a, int b) {
        return s[a] > s[b];
    }
};

typedef priority_queue<int, vector<int>, Cmp> pq;
pq pri;

int main() {

    while ( scanf("%s", c) != EOF ) {
        cn = strlen(c);
        pq().swap(pri);

        for (int ci = 0; ci < cn; ci++) {
            s[ci] = c[ci];
            ed[ci] = ci;
            pri.push(ci);
        }

        int k;
        scanf("%d", &k);

        for (int ki = 0; ki < k; ki++) {
            if ( pri.empty() ) {
                puts("No such line.");
                break;
            }

            int t = pri.top();
            pri.pop();

            if ( ki+1 == k ) puts(s[t].c_str() );

            ed[t]++;
            if ( ed[t] != cn ) {
                s[t].push_back(c[ed[t] ] );
                pri.push(t);
            }
        }
    }
}

沒有留言:

張貼留言