ARC#058 F Iroha Loves Strings(欲張り+文字列処理+dp前処理)

問題面はここのネット上で問題解が見つからないでしょう.そこで私は自分である大物のacコードに対してinfを見てからやっと分かった.
に言及
小CにはN個の文字列s 1,s 2,s 3,...,sN s 1 , s 2 , s 3 , . . . , s N、そして彼はいくつかの文字列を選択して順次接続するつもりです.得ることができるすべての文字列の中で長さKの辞書の順序が最も小さいことを聞きます.N≤2000,K≤104 N ≤ 2000 , K ≤ 10 4 . s 1 s 3 s 1 s 3が得られ、s 3 s 1 s 3 s 1が得られない.
やり方
欲張りな考え:毎回1つの長さの最も長い列を保存し、辞書の順序が最も小さい.この辞書順の比較には長さは含まれません.すなわち,2つの列に真の包含関係がある場合は,長さの大きいその列をとる.1つの列sを加えるたびに、元の列に接頭辞を取って、sをつなぎ合わせます.すべての可能な接合方法の中で最適なものを選択します.しかし、長さはk k kである必要があるという制限があるので、i~n列で綴ることができる長さをdpで前処理し、毎回合法的な案だけを取ることで、最終的に綴るのはk kであることを保証することができるという考えがある.また辞書順を比較する場合は,2つの列のlcp長を求め,lcp+1ビットの場所の大きさを比較する必要がある.そのためexkmpが必要です.具体的にはコード注釈~この問題を自分で理解しなければならないところがあるような気がします.
コード#コード#

/*
*      ；
*       ；
*               lcp；
*       ；
*/
#include
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
#define N 2005
#define M 10005
#define ll long long
using namespace std;
int n, m, len, tp, tot, a[N], q[M], f[M<<1];
char s[N][M], s1[M<<1], ch[M];
bool fl[N][M], ok[M], vis[M];
struct node {
    int x, y; node() {}//x,y  ， ch    x   a[i]   
    node(int a, int b) { x = a, y = b; }
} b[M];
inline void exkmp(char s[], int n) {
    int k = 1; memset(f, 0, sizeof f); f[1] = n;//      ，    f[1] = 0;
    rep(i, 2, n) {
        f[i] = max(0, min(k+f[k]-i, f[i-k+1]));
        while(i+f[i] <= n && s[f[i]+i] == s[f[i]+1]) f[i]++;
        if(k == 1 || f[i]+i > f[k]+k) k = i;
    }
}
inline int cmp(const node &u, const node &v) {//    ，-1/0/1  =/>，            
    if(!u.y && !v.y) return 0;
    if(!u.y) return -cmp(v, u);
    if(!v.y) {
        if(v.x < u.x) return 0;
        int t = f[u.x+u.y+1];
        if(u.x+t >= v.x) return 0;
        return s1[t+1] < s1[u.x+u.y+t+1] ? -1 : 1;
    }
    if(u.x == v.x) return 0;
    if(u.x > v.x) return -cmp(v, u);
    int t = f[u.x+u.y+1];
    if(u.x+t <= v.x) return s1[t+1] < s1[u.x+u.y+t+1] ? -1 : 1;
    t = f[v.x-u.x+1];
    if(v.x+t >= u.x) return 0;
    return s1[v.x-u.x+t+1] < s1[t+1] ? -1 : 1;
}
bool operator < (const node &x, const node &y) { return cmp(x, y) < 0; }
bool operator == (const node &x, const node &y) { return !cmp(x, y); }
int main() {
    scanf("%d%d", &n, &m);//a[i]  i     
    rep(i, 1, n) { scanf("%s", s[i]+1); a[i] = strlen(s[i]+1); }
    fl[n+1][0] = 1;//fl[i][j]  i n           j  
    per(i, n, 1) rep(j, 0, m) {
        fl[i][j] = fl[i+1][j];//   i  
        if(j >= a[i]) fl[i][j] |= fl[i+1][j-a[i]];//  i  
    }
    //ch      【           】 【  】  ，          m   
    //ok[i]=1        ，len    
    len = 0; ok[0] = 1;
    rep(i, 1, n) {
        if(!len) {
            if(fl[i+1][m-a[i]]) rep(j, 1, a[i]) ch[++len] = s[i][j];
            ok[len] = 1; continue;
        }
        //    s[i]      ch   ，exkmp              lcp， f  
        tot = 0;
        rep(j, 1, a[i]) s1[++tot] = s[i][j];//s1       
        rep(j, 1, len) s1[++tot] = ch[j];
        exkmp(s1, tot);
        memset(vis, 0, sizeof vis);
        rep(j, 0, m) if(fl[i+1][m-j]) {//   i          
            if(ok[j]) { vis[j] = 1; b[j] = node(j, 0); }
            if(j >= a[i] && ok[j-a[i]]) {
                if(vis[j]) b[j] = min(b[j], node(j-a[i], a[i]));
                else { vis[j] = 1; b[j] = node(j-a[i], a[i]); }
            }
        }
        q[1] = 0; tp = 1;
        rep(j, 1, m) if(vis[j]) {
            while(tp > 1 && b[j] < b[q[tp]]) tp--;
            if(b[j] == b[q[tp]]) q[++tp] = j;
        }//   '=='          ，      ，    
        len = q[tp];
        if(b[len].y) rep(j, 1, a[i]) ch[b[len].x+j] = s[i][j];
        ch[len+1] = 0;
        memset(ok, 0, sizeof ok);
        while(tp) ok[q[tp--]] = 1;
    }//                    m ，           m
    printf("%s
", ch+1);
    return 0;
}