@spoj - [email protected] Longest Common Substring

目录

• @[email protected]
• @[email protected]
• @accepted [email protected]
• @[email protected]

@[email protected]

求两个仅由小写字母构成的字符串的最长公共子串。

input
两行。每行一个不超过 250000 个小写字母的字符串。

output
最长公共子串长度。如果没有，输出 0。

sample input
alsdfkjfjkdsal
fdjskalajfkdsla
sample output
3

@[email protected]

其实有一个不涉及任何字符串算法的简单算法。我们发现公共子串的长度是单调的（即大公共串的子串也是公共串），因此我们可以对第二个串进行滑动窗口。只是这个算法需要判断一个串是否为另一个串的子串，所以很慢。
但是这个算法可以帮助我们理解后缀自动机的过程。

后缀自动机中，我们将所有结点都设置为可接受的结点，那么可接受的串就是所有的子串。
因此我们可以将第二个串放到第一个串建成的后缀自动机上跑。如果跑不动了就沿着 fa 跳。
可以发现这个过程其实跟滑动窗口特别像。跑后缀自动机就是移动右端点，沿着 fa 跳就是移动左端点。

@accepted [email protected]

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 250000;
struct sam{
    sam *ch[26], *fa; int mx;
}pl[2*MAXN + 5], *tcnt, *root, *lst;
void init() {
    lst = tcnt = root = &pl[0];
    for(int i=0;i<26;i++)
        root->ch[i] = NULL;
    root->fa = NULL, root->mx = 0;
}
sam *newnode() {
    tcnt++;
    for(int i=0;i<26;i++)
        tcnt->ch[i] = NULL;
    tcnt->fa = NULL, tcnt->mx = 0;
    return tcnt;
}
void sam_extend(int x) {
    sam *cur = newnode(), *p = lst;
    cur->mx = lst->mx + 1; lst = cur;
    while( p && !p->ch[x] )
        p->ch[x] = cur, p = p->fa;
    if( !p )
        cur->fa = root;
    else {
        sam *q = p->ch[x];
        if( q->mx == p->mx + 1 )
            cur->fa = q;
        else {
            sam *cne = newnode();
            (*cne) = (*q); cne->mx = p->mx + 1;
            q->fa = cur->fa = cne;
            while( p && p->ch[x] == q )
                p->ch[x] = cne, p = p->fa;
        }
    }
}
char S[MAXN + 5], T[MAXN + 5];
int main() {
    init();
    scanf("%s%s", S, T);
    int lenS = strlen(S), lenT = strlen(T);
    for(int i=0;i<lenS;i++)
        sam_extend(S[i] - ‘a‘);
    int ans = 0, res = 0; sam *nw = root;
    for(int i=0;i<lenT;i++) {
        while( nw && !nw->ch[T[i] - ‘a‘] )
            nw = nw->fa;
        if( !nw ) nw = root;
        else res = min(res, nw->mx), nw = nw->ch[T[i] - ‘a‘], res++;
        ans = max(ans, res);
    }
    printf("%d\n", ans);
}

@[email protected]

注意一下每次去更新答案的不是 nw->mx 而是我们中途一直维护的一个变量 res，至于这个变量的意义可以像我说的一样用滑动窗口的方式去理解。