XIII Open Championship Problem E. Enter the Word Problem 后缀自动机+贪心

Problem E. Enter the Word 后缀自动机+贪心

Source

XIII Open Championship of Y.Kupala Grodno SU
Grodno, Saturday, April 29, 2017

My Solution

题意：这里对于生成一个字符串有2种操作，1、在末尾添加一个字母，花费代价为 1；2、在末尾添加一个substr，且该substr为已存在字符串的子串，花费代价为 1。

现给出需要构造出的字符串，为最小的构造代价。

贪心+后缀自动机

贪心策略是 对于剩下的字符串suf，取它的最大前缀 substr，且substr是已构造出的字符串pre的子串，如果substr为空则执行操作1，否则执行操作2，这样每次都添加尽可能多的字母，所以代价是最少的。

所以对于前缀pre建立后缀自动机，每次把suf丢进去匹配，其最大的 后缀的前缀 即为我们要求的 substr，然后一次把substr添加到sam里。

时间复杂度 O(n)

空间复杂度 O(2*n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 2*2*1e5 + 8;

string s;
struct SAM{
    int ch[MAXN][26], pre[MAXN], val[MAXN];
    int last, tot, minl[MAXN], maxl[MAXN];
    void init(){
        last = tot = 0;
        memset(ch[0], -1, sizeof ch[0]);
        pre[0] = -1; val[0] = 0;
        minl[0] = maxl[0] = 0;
    }
    void extend(int c){
        int p = last, np = ++tot;
        val[np] = val[p] + 1;
        memset(ch[np], -1, sizeof ch[np]);
        minl[np] = maxl[np] = val[np];
        while(~p && ch[p][c] == -1) ch[p][c] = np, p = pre[p];
        if(p == -1) pre[np] = 0;
        else{
            int q = ch[p][c];
            if(val[q] != val[p] + 1){
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                val[nq] = val[p] + 1;
                minl[nq] = maxl[nq] = val[nq];
                pre[nq] = pre[q];
                pre[q] = pre[np] = nq;
                while(~p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
            }
            else pre[np] = q;
        }
        last = np;
    }
    int _find(const string &s){
        int sz = s.size(), u = 0, c, i;
        for(i = 0; i < sz; i++){ c = s[i] - 'a'; if(~ch[u][c]) u = ch[u][c]; else{ return i; } } return sz; } } sam; int main() { #ifdef LOCAL //freopen("e.txt", "r", stdin); //freopen("e.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, sz, i, j, x; int ans = 0; cin >> s;
    sz = s.size();
    sam.init();
    for(i = 0; i < sz; i++){
        j = sam._find(s.substr(i, sz - i));
        x = i + j;
        //cout << i << " " << j << " " << x << endl;
        if(j == 0){
            sam.extend(s[i] - 'a');
            ans++;
        }
        else{
            ans++;
            for(; i < x; i++){
                sam.extend(s[i] - 'a');
            }
            if(i != sz)i--;
        }

    }
    cout << ans << "n";

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx