记录编号	554868	评测结果	AAAAAAAAAA
题目名称	[POJ2774]很长的信息	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2020-09-21 21:20:21	内存使用	22.92 MiB

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define Inf 1e9
const int maxn = 150000;
struct SAM{
    int val, root;
    int next[26];
}a[maxn << 1];
int RT, cnt, Last;
char s[maxn];

void Extend(int c){
    int p = Last, np = ++cnt;
    a[np].val = a[p].val + 1;
    while(p && !a[p].next[c]){
        a[p].next[c] = np;
        p = a[p].root;
    }
    if(!p) a[np].root = RT;
    else {
        int q = a[p].next[c];
        if(a[q].val == a[p].val + 1) a[np].root = q;
        else {
            int nq = ++cnt; a[nq] = a[q];
            a[nq].val = a[p].val + 1;
            a[q].root = a[np].root = nq;
            while(p && a[p].next[c] == q){
                a[p].next[c] = nq;
                p = a[p].root;
            }
        }
    }
    Last = np;
}
void Init();
int main(){
    freopen("longlongmessage.in", "r", stdin);
    freopen("longlongmessage.out", "w", stdout);
    Init();
    return 0;
}
void Init(){
    RT = Last = ++cnt;
    scanf("%s", s);
    int len = strlen(s);
    for(int i = 0; i < len; i++){
        Extend(s[i]-'a');
    }
    scanf("%s", s);
    len = strlen(s);
    int now = RT, nowLen = 0, ans = 0;
    for(int i = 0; i < len; i++){
        int c = s[i] - 'a';
        if(a[now].next[c]){
            now = a[now].next[c];
            nowLen++;
        }else{
            while(now && !a[now].next[c]) now = a[now].root;
            if(now) {
                nowLen = a[now].val + 1;
                now = a[now].next[c];
            }else {
                now = RT;
                nowLen = 0;
            }
        }
        ans = max(ans, nowLen);
    }
    printf("%d\n", ans);
}