原题链接

题意明确说明求两字符串的最长连续公共子串，可用字符串hash或者后缀数据结构来做

关于后缀树

后缀树的原理较为简单，但 \(o(n)\) 的构建算法（Ukkonen算法）稍难理解，可参考以下博文

https://www.cnblogs.com/xubenben/p/3484988.html

• 在此也特别感谢该作者，本人也参考了上述文章作者的讲解，可以从我后面的代码看出和作者的代码步骤是一样的。我的代码主要体现的是对本题的dfs阶段的处理

思路

• 1.获得两个字符串ss1,ss2之后，将其拼接为\(ss1\) + "{" + \(ss1\) + "|",之所以选择这两个字符是因为其ascii码紧跟在'z'之后，对存储空间较为友好

• 2.对合串建立后缀树

• 3.遍历后缀树，记录经过的字符串长度，对找到一个经过的长度最长的非叶子节点，这个节点要同时满足：

  • 有一个子树中包含{（当然这样的话必然包含|），说明这个节点属于ss1
  • 有一个子树中包含|（并且不包含{），说明这个节点属于ss2

同时满足，说明从根到此节点的路程，经过的全是公共子串，可以根据记录的字符串长度更新答案

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

const int maxn = (1 << 30);
const int root = 1;

char ss[200010] = {0};
char ss2[100005] = {0};
int act = 1, co = 1;
int acteg = -1;
int tep = 0;
int ind = 0, rem = 0, s_end = -1;
int links[100005] = {0};
int vv[100005] = {0};
int mm = 0;
int linkk = 0;
int len1 = 0, len2 = 0;

int ans = 0;    //本题答案 

struct ab
{
    int l;
    int r;
    int nex;
    int alp[28];        // 后面26 27 下标代表的字符是 ‘{’和  ‘|’
} tree[1000005];        // 作为分割与结束符 (ascii相邻防止越界)

int add_new(int o, int ll = s_end, int rr = maxn)
{
    tree[o].l = ll;
    tree[o].r = rr;
    return o;
}

void add_link(int o)
{
    if (linkk)
    {
        tree[linkk].nex = o;
    }
    linkk = o;
}

int check_len(int o)
{
    return min(tree[o].r, s_end) - tree[o].l + 1;
}

bool check_contain(int o)
{
    int node_len = check_len(o);
    if (node_len <= ind)
    {
        ind -= node_len;
        tep += node_len;
        act = o;
        return true;
    }
    return false;
}

void add(char cc)
{
    ++rem;
    linkk = 0;
    while (rem > 0)
    {
        if (!ind)
        {
            tep = s_end;
        }
        int& actedge_node = tree[act].alp[ss[tep] - 'a'];
        if (!actedge_node)
        {
            actedge_node = add_new(++co, s_end);
            add_link(act);
        }
        else
        {
            if (check_contain(actedge_node))
            {
                continue;
            }
            else
            {
                if (ss[tree[actedge_node].l + ind] != cc)   // 分裂注意原树(actedge_node)必须成为子树（否则会和原先的子树失去联系）
                {
                    int leaf1 = add_new(++co, s_end);
                    int leaf2 = actedge_node;
                    int newtree = add_new(++co, tree[actedge_node].l, tree[actedge_node].l + ind - 1);
                    tree[newtree].alp[cc - 'a'] = leaf1;
                    tree[newtree].alp[ss[tree[actedge_node].l + ind] - 'a'] = leaf2;
                    tree[leaf2].l += ind;
                    actedge_node = newtree;
                    add_link(actedge_node);
                }
                else
                {
                    ++ind;      // 活跃半径只在此处增加 ，增加完就加链并结束本次增点
//                    if (act != root)
//                    {
                        add_link(act);
//                    }
                    break;
                }
            }
        }
        --rem;
        if (act == root)
        {
            if (!ind)
            {
                break;
            }
            tep = s_end - rem + 1;
            --ind;
        }
        else
        {
//            ind = rem - 1;
//            tep = s_end - rem + 1;
            if (tree[act].nex)
            {
                act = tree[act].nex;
            }
            else
            {
                act = root;
            }
        }
    }
}

int dfs(int o, int cc)        // 本题所需的搜索 返回1代表包含{，2代表包含|，3代表都有
{
    bool bk1 = false;
    bool bk2 = false;
    bool stop = false;
    for (int i = 0; i <= 27; ++i)
    {
        if (tree[o].alp[i])
        {
            if (tree[tree[o].alp[i]].r != maxn)
            {
                int contain_terminal = dfs(tree[o].alp[i], cc + check_len(tree[o].alp[i]));
                if (contain_terminal == 1)
                {
                    bk1 = true;
                }
                if (contain_terminal == 2)
                {
                    bk2 = true;
                }
                if (contain_terminal == 3)
                {
                    bk1 = bk2 = true;
                    stop = true;
                }
            }
            else
            {
                if (tree[tree[o].alp[i]].l > len1)
                {
                    bk2 = true;
                }
                else
                {
                    bk1 = true;
                }
            }
        }
    }
    if (stop)
    {
        return 3;
    }
    if (bk1 && bk2)
    {
        ans = max(ans, cc);
        return 3;
    }
    if (bk1)
    {
        return 1;
    }
    if (bk2)
    {
        return 2;
    }
}

int main()
{
    scanf("%s%s", ss, ss2);
    len1 = strlen(ss);
    len2 = strlen(ss2);
    ss[len1] = '{';                 //ss1的结束符，防止两字符串后缀拼接
    for (int i = len1 + 1; i <= len1 + len2; ++i)
    {
        ss[i] = ss2[i - len1 - 1];
    }
    ss[len1 + len2 + 1] = '|';      //ss2的结束符（也是整个合串的结束符）
    for (int i = 0; i <= len1 + len2 + 1; ++i)
    {
        ++s_end;
        add(ss[i]);
    }
    dfs(root, 0);
    printf("%d", ans);
    return 0;
}