求多串的最长公共字串.

法1: 二分长度+hash 传送门

法2: 二分+后缀数组传送门

法3: 后缀自动机

拿第一个串建自动机,然后用其他串在上面匹配.每次求出SAM上每个节点的最长匹配长度后,再在全局取最小值(因为是所有串的公共串)就行了.

CODE

#include<bits/stdc++.h>

using namespace std;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

	char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;

	for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 2005;

const int C = 26;

int m, lk[MAXN<<1], ch[MAXN<<1][C], len[MAXN<<1], mx[MAXN<<1], mn[MAXN<<1], bin[MAXN<<1], seq[MAXN<<1], sz, last;

inline void init() {

    last = sz = 0; ++sz;

    lk[0] = -1; len[0] = 0;

}

inline void Copy(int A, int B) {

    lk[A] = lk[B];

    memcpy(ch[A], ch[B], sizeof ch[B]);

}

inline int insert(int p, int c) {

    int cur = sz++; last = cur;

    len[cur] = len[p] + 1;

    for(; ~p && !ch[p][c]; p = lk[p]) ch[p][c] = cur;

    if(p == -1) lk[cur] = 0;

    else {

        int q = ch[p][c];

        if(len[p] + 1 == len[q]) lk[cur] = q;

        else {

            int x = sz++;

            len[x] = len[p] + 1;

            Copy(x, q);

            lk[cur] = lk[q] = x;

            for(; ~p && ch[p][c] == q; p = lk[p]) ch[p][c] = x;

        }

    }

    return last;

}

inline void Match(char *s) {

    int p = 0, now = 0, j = 0;

    for(int c; s[j]; ++j) {

        if(ch[p][c=s[j]-'a'])

            ++now, p = ch[p][c];

        else {

            for(; ~p && !ch[p][c]; p = lk[p]);

            if(p == -1) now = p = 0;

            else now = len[p] + 1, p = ch[p][c];

        }

        mx[p] = max(mx[p], now);

    }

    for(int i = sz-1; i; --i) {

        mn[seq[i]] = min(mn[seq[i]], mx[seq[i]]);

        mx[lk[seq[i]]] = max(mx[lk[seq[i]]], mx[seq[i]]);

        mx[seq[i]] = 0;

    }

}

char s[MAXN];

int main() {

	read(m); scanf("%s", s);

	if(--m == 0) return printf("%d\n", strlen(s)), 0;

	init(); int p = 0;

	for(int i = 0; s[i]; ++i) p = insert(p, s[i]-'a');

    for(int i = 0; i < sz; ++i) ++bin[mn[i] = len[i]];

    for(int i = 1; i < sz; ++i) bin[i] += bin[i-1];

    for(int i = sz-1; ~i; --i) seq[--bin[len[i]]] = i;

	while(m--) scanf("%s", s), Match(s);

    int ans = 0;

	for(int i = 1; i < sz; ++i)

        ans = max(ans, mn[i]);

    printf("%d\n", ans);

}

巴特西

BZOJ 2946 [Poi2000]公共串 (二分+Hash/二分+后缀数组/后缀自动机)

CODE

最新文章

热门文章