还是模板啊，手残&&打成||查错查了1h+TAT
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 2000003;
int t1[N], t2[N], c[N];
void st(int *x, int *y, int *sa, int n, int m) {
int i;
for(i = 0; i < m; ++i) c[i] = 0;
for(i = 0; i < n; ++i) ++c[x[y[i]]];
for(i = 1; i < m; ++i) c[i] += c[i - 1];
for(i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
}
void mkhz(int *a, int *sa, int n, int m) {
int i, j, p, *t, *x = t1, *y = t2;
for(i = 0; i < n; ++i) x[i] = a[i], y[i] = i;
st(x, y, sa, n, m);
for(p = 1, j = 1; p < n; j <<= 1, m = p) {
for(p = 0, i = n - j; i < n; ++i) y[p++] = i;
for(i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
st(x, y, sa, n, m);
for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j] ? p - 1 : p++;
}
}
void mkh(int *r, int *sa, int *rank, int *h, int n) {
int i, j, k = 0;
for(i = 1; i <= n; ++i) rank[sa[i]] = i;
for(i = 1; i <= n; h[rank[i++]] = k)
for(k ? --k : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; ++k);
}
char s[N];
int a[N], sa[N], h[N], rank[N], n;
int main() {
while(~scanf("%s", s + 1)) {
int tmp = strlen(s + 1);
s[tmp + 1] = '$';
scanf("%s", s + tmp + 2);
int n = strlen(s + 1);
for(int i = 1; i <= n; ++i) a[i] = s[i];
mkhz(a, sa, n + 1, 130);
mkh(a, sa, rank, h, n);
int ans = 0;
++tmp;
for(int i = 2; i <= n; ++i)
if (((tmp < sa[i - 1] && tmp > sa[i]) || (tmp < sa[i] && tmp > sa[i - 1])) && h[i] > ans)
ans = h[i];
printf("%d
", ans);
}
return 0;
}
Orz