SPOJ 1811 Longest Common Substring(后缀自动机)

偏执的太偏执、 2022-03-29 08:42 77阅读 0赞

题目链接：[http://www.spoj.com/problems/LCS/][http_www.spoj.com_problems_LCS]

题意：求两个串的最长公共substring。

思路：建立一个串的SAM，对于第二个串的每个前缀，找到其在第一个串上匹配的最大长度。

const int KIND=26;
    struct SAM
    {
        SAM *son[KIND],*pre;
        int len,cnt;
    
        void init()
        {
            clr(son,NULL);
            pre=NULL;
            len=0;
        }
    };
    
    SAM sam[N],*head,*last,*b[N];
    int d[N],cnt,f[N],len;
    char s[N];
    
    void initSAM()
    {
        sam[0].init();
        head=last=&sam[0];
        cnt=1;
    }
    
    
    void insert(int x)
    {
        SAM *p=&sam[cnt++],*u=last;
        p->len=last->len+1;
        last=p;
        for(;u&&!u->son[x];u=u->pre) u->son[x]=p;
        if(!u) p->pre=head;
        else if(u->son[x]->len==u->len+1) p->pre=u->son[x];
        else
        {
            SAM *r=&sam[cnt++],*q=u->son[x];
            *r=*q; r->len=u->len+1;
            p->pre=q->pre=r;
            for(;u&&u->son[x]==q;u=u->pre) u->son[x]=r;
        }
    }
    
    int main()
    {
        RD(s);
        len=strlen(s);
        initSAM();
        int i;
        FOR0(i,len) insert(s[i]-'a');
        RD(s); len=strlen(s);
        int ans=0,x,L=0;
        SAM *p=head;
        FOR0(i,len)
        {
            x=s[i]-'a';
            if(p->son[x]) L++,p=p->son[x];
            else
            {
                while(p&&!p->son[x]) p=p->pre;
                if(p) L=p->len+1,p=p->son[x];
                else p=head,L=0;
            }
            ans=max(ans,L);
        }
        PR(ans);
        return 0;
    }

[http_www.spoj.com_problems_LCS]: http://www.spoj.com/problems/LCS/

发表评论取消回复

表情：

评论列表（有 0 条评论，77人围观）

还没有评论，来说两句吧...

相关阅读

相关【字符串】后缀自动机

参考博客： https://www.luogu.org/problemnew/solution/P3804 转载于:https://www.cnblogs.com/Aiah

痛定思痛。/ 2023年08月17日 16:25/ 0 赞/ 55 阅读

相关 POJ 3415 Common Substrings【后缀自动机】

max：即代码中 len 变量，它表示该状态能够接受的最长的字符串长度。 min：表示该状态能够接受的最短的字符串长度。实际上等于该状态的 fail 指针指向的结点的 le

拼搏现实的明天。/ 2022年08月08日 14:56/ 0 赞/ 102 阅读

相关 SPOJ Longest Common Substring II

求十个串的最长连续公共子串。第一个串建立自动机。用其它每个串在自动机上跑一遍，记录每个状态上能匹配的最长长度。然后求每个状态匹配长度的最小值。注意每个状态

素颜马尾好姑娘i/ 2022年08月04日 04:26/ 0 赞/ 82 阅读

相关后缀自动机详解

转载自：[点我][Link 1] 原论文（俄文）地址：[suffix\_automata][suffix_automata] 后缀自动机后缀自动机（单词的有向

川长思鸟来/ 2022年05月16日 08:20/ 0 赞/ 363 阅读

相关 SPOJ 1811 Longest Common Substring(后缀自动机)

题目链接：[http://www.spoj.com/problems/LCS/][http_www.spoj.com_problems_LCS] 题意：求两个串的最长公共su

偏执的太偏执、/ 2022年03月29日 08:42/ 0 赞/ 78 阅读

相关 Longest Common Substring II SPOJ - LCS2

A string is finite sequence of characters over a non-empty finite set Σ. In this proble

太过爱你忘了你带给我的痛/ 2021年12月10日 10:43/ 0 赞/ 86 阅读

相关后缀自动机之lcs

题意，给定两个字符串，求他们的最大的连续公共子串的长度是多少，数据范围是1--n 以前有一个DP思路，但是今天可以使用后缀自动机来写。首先对其中一个串a构造后缀自动机，然

Dear 丶/ 2021年11月19日 13:50/ 0 赞/ 284 阅读

相关 Substrings SPOJ - NSUBSTR （后缀自动机）

Substrings \\\[ Time Limit: 100ms\\quad Memory Limit: 1572864 kB \\\] 题意给出一个长度为

心已赠人/ 2021年11月09日 23:10/ 0 赞/ 232 阅读

相关后缀自动机学习

1. [hihocoder \1441 : 后缀自动机一·基本概念][hihocoder _1441 _] 按照后缀自动机概念模拟即可, 复杂度$O(n^3logn)$.

深碍√TFBOYSˉ_/ 2021年11月05日 22:38/ 0 赞/ 252 阅读

相关 SPOJ- Distinct Substrings(后缀数组&后缀自动机)

Given a string, we need to find the total number of its distinct substrings. Input T

一时失言乱红尘/ 2021年11月01日 05:30/ 0 赞/ 248 阅读