再论后缀自动机

在之前已经对后缀自动机的概念进行了阐述
后缀数组与后缀自动机

其实这种思想有很多应用
对这个算法的构造和思考如下

后缀自动机构造原理

LCS问题的O(nlogn)解法

HDU1159

const int maxn = 1000 + 5;
char A[maxn], B[maxn];

vector<int> loc[maxn];
vector<int> C, D;

void init() {
    _for(i, 0, maxn) loc[i].clear();
    C.clear();
    D.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%s%s", A, B) != EOF) {
        init();

        int lenA = strlen(A), lenB = strlen(B);


        _forDown(i, lenB - 1, 0) loc[B[i] - 'a'].push_back(i);
        _for(i, 0, lenA) {
            int x = A[i] - 'a';
            if(loc[x].empty()) continue;
            _for(j, 0, loc[x].size()) {
                C.push_back(loc[x][j]);
            }
        }

        if(!C.empty()) {
            D.push_back(C[0]);
            _for(i, 1, C.size()) {
                if(C[i] > D.back()) D.push_back(C[i]);
                else {
                    vii it = lower_bound(D.begin(), D.end(), C[i]);
                    *it = C[i];
                }
            }
        }

        cout << D.size() << endl;
    }
}

LCS问题的O(n)算法

LCS

const int maxl = 250005;
const int maxn = maxl * 2;


class SAM {
public:
    int sz, last;
    int trans[maxn][26], link[maxn], maxlen[maxn];

    SAM() {
        Set(trans, 0);
        Set(link, 0);
        Set(maxlen, 0);

        sz = last = 1;
    }

    void extend(int ch) {
        int cur = ++sz, p = last;
        maxlen[cur] = maxlen[p] + 1;

        for( ; p && trans[p][ch] == 0; p = link[p]) trans[p][ch] = cur;

        if(p == 0) link[cur] = 1;
        else {
            int q = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
            else {
                int clone = ++sz;
                maxlen[clone] = maxlen[p] + 1;

                Cpy(trans[clone], trans[q]);
                link[clone] = link[q];

                for( ; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
                link[q] = link[cur] = clone;
            }
        }

        last = cur;
    }

    int LCS(const char* str) {
        int len = strlen(str);
        int lcs = 0, tmplen = 0;
        int cur = 1;

        _for(i, 0, len) {
            int x = str[i] - 'a';
            if(trans[cur][x]) {
                cur = trans[cur][x];
                tmplen++;
            }
            else {
                while (cur && trans[cur][x] == 0) cur = link[cur];
                if(cur) {
                    tmplen = maxlen[cur] + 1;
                    cur = trans[cur][x];
                }
                else {
                    tmplen = 0;
                    cur = 1;
                }
            }
            lcs = max(lcs, tmplen);
        }
        return lcs;
    }
};

SAM sam;

int main() {
    freopen("input.txt", "r", stdin);
    char A[maxl], B[maxl];
    scanf("%s%s", A, B);
    int lenA = strlen(A), lenB = strlen(B);

    _for(i, 0, lenA) sam.extend(A[i] - 'a');
    cout << sam.LCS(B) << endl;

}

SAM根据maxlen对节点排序

SAM求子串出现次数

子串的长度为k
比如ababa, 有很多长度为3的子串
其中’aba’出现2次, ‘bab’出现1次

求长度为k的子串
最多可能出现多少次？

Substrings

SAM和拓扑排序(BFS版本)

这种写法会超时

SAM sam;

vector<int> G[maxn];
int indeg[maxn];
llong ans[maxn];

void init() {
    Set(cnt, 0);
    Set(ans, 0);
    Set(indeg, 0);
}

void build() {
    _rep(i, 1, sam.sz) {
        G[i].push_back(sam.link[i]);
        indeg[sam.link[i]]++;
    }
}

void topo() {
    queue<int> que;
    _rep(i, 0, sam.sz) if(indeg[i] == 0) que.push(i);

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        _for(i, 0, G[u].size()) {
            int v = G[u][i];
            cnt[v] += cnt[u];

            if(--indeg[v] == 0) que.push(v);
        }
    }

    _rep(i, 1, sam.sz) ans[sam.maxlen[i]] = max(ans[sam.maxlen[i]], cnt[i]);
}

// usage: build() topo()

int main() {
    freopen("input.txt", "r", stdin);
    init();

    char str[maxl];
    scanf("%s", str);
    int len = strlen(str);

    _for(i, 0, len) sam.extend(str[i] - 'a');

    build();
    topo();
    _forDown(i, len, 1) ans[i] = max(ans[i], ans[i + 1]);
    _rep(i, 1, len) cout << ans[i] << endl;
}

用RadixSort优化拓扑排序

从小到大的排序, 按照 maxlen 的排名
maxlen 从 [0, len], 序号依次是 {1, 2, ..., sam.sz}

const int maxl = 250000 + 5;
const int maxn = maxl * 2;

llong cnt[maxn];
int len;

class SAM {
public:
    int maxlen[maxn], link[maxn], trans[maxn][26];
    int last, sz;

    SAM() {
        Set(maxlen, 0);
        Set(link, 0);
        Set(trans, 0);

        last = sz = 1;
    }

    void extend(int ch) {
        int cur = ++sz, p = last;
        maxlen[cur] = maxlen[p] + 1;
        cnt[cur] = 1;

        for( ; p && trans[p][ch] == 0; p = link[p]) trans[p][ch] = cur;

        if(p == 0) link[cur] = 1;
        else {
            int q = trans[p][ch];
            if(maxlen[q] == maxlen[p] + 1) link[cur] = q;
            else {
                int clone = ++sz;
                maxlen[clone] = maxlen[p] + 1;

                Cpy(trans[clone], trans[q]);
                link[clone] = link[q];

                for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
                link[q] = link[cur] = clone;
            }
        }

        last = cur;
    }
};

SAM sam;

// use Radix sort instead of bfs-topoSort


int C[maxn];
int id[maxn];
llong ans[maxn];

void init() {
    Set(cnt, 0);
    Set(C, 0);
    Set(id, 0);
    Set(ans, 0);
}

void rsort() {
    Set(C, 0);
    _rep(i, 1, sam.sz) C[sam.maxlen[i]]++;
    _rep(i, 1, len) C[i] += C[i - 1];
    _forDown(i, sam.sz, 1) id[C[sam.maxlen[i]]--] = i;

    _forDown(i, sam.sz, 1) {
        int u = id[i];
        cnt[sam.link[u]] += cnt[u];
    }
}

void solve() {
    _rep(i, 1, sam.sz) ans[sam.maxlen[i]] = max(ans[sam.maxlen[i]], cnt[i]);
    _forDown(i, len, 1) ans[i] = max(ans[i], ans[i + 1]);
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    char str[maxl];
    scanf("%s", str);
    len = strlen(str);

    _for(i, 0, len) sam.extend(str[i] - 'a');

    rsort();
    solve();
    _rep(i, 1, len) printf("%d\n", ans[i]);

}

值得注意的是

cnt[suffix]随着len的增加, 是递减的
所以刷cnt[i]的值的时候, 从大的len往小的len刷

for(int i = sam.sz; i >= 1; i--) {
    // 找到排名最靠后的点, 也就是len最长的点
    int u = id[i];
    cnt[sam.link[u]] += cnt[u];
}

endpos()性质