题目大意:
给定三个字符串s1,s2,s3,求一个字符串w满足:
- w是s1的子串
- w是s2的子串
- s3不是w的子串
- w的长度应尽可能大
题解:
首先我们可以用AC自动机找出s3在s1,s2中出现的位置(窝不会kmp)
不完全包括特定区间的最长公共子串了.
我们二分一下答案的长度k
于是我们发现问题变成了:
- 给定两个字符串,有一些点不能选择,问是否存在两个点所代表后缀的LCP >= k
所以我们将两个字符串拼接起来,有后缀自动机建立后缀树
然后在后缀树上O(n)dp一边便可处理
(O(nlogn))
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
namespace ACM{
const int maxn = 10010;
int ch[maxn][26],nodecnt;
bool danger[maxn];
inline void insert(char *s){
int nw = 0;
for(int i=0,c;s[i] != 0;++i){
c = s[i] - 'a';
if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;
nw = ch[nw][c];
}danger[nw] = true;
}
int q[maxn],l,r,fail[maxn];
inline void build(){
l = 0;r = -1;fail[0] = 0;
for(int c=0;c<26;++c){
if(ch[0][c]){
fail[ch[0][c]] = 0;
q[++r] = ch[0][c];
}
}
while(l <= r){
int u = q[l++];
for(int c=0;c<26;++c){
int t = ch[fail[u]][c];
if(ch[u][c] == 0) ch[u][c] = t;
else{
fail[ch[u][c]] = t;
q[++r] = ch[u][c];
}
}
}
}
}
namespace Graph{
const int maxn = 210010;
struct Node{
int to,next;
}G[maxn];
int head[maxn],cnt;
void add(int u,int v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
}
namespace SAM{
const int maxn = 210010;
struct Node{
int nx[27];
int len,fa,x;
}T[maxn];
int last,nodecnt;
inline void init(){
T[last = nodecnt = 0].fa = -1;
}
inline void insert(char cha,int i){
int c = cha - 'a',cur = ++nodecnt,p;
T[cur].len = T[last].len + 1;
for(p = last;p != -1 && T[p].nx[c] == 0;p = T[p].fa) T[p].nx[c] = cur;
if(p == -1) T[cur].fa = 0;
else{
int q = T[p].nx[c];
if(T[q].len == T[p].len + 1) T[cur].fa = q;
else{
int co = ++ nodecnt;
T[co] = T[q];T[co].len = T[p].len + 1;
for(;p != -1 && T[p].nx[c] == q;p = T[p].fa) T[p].nx[c] = co;
T[cur].fa = T[q].fa = co;
}
}T[last = cur].x = i;
}
}
const int maxn = 210010;
char s1[maxn],s2[maxn],s3[maxn];
bool flag1[maxn],flag2[maxn];
int len1,len2,w,mid;
inline void work1(){
using namespace ACM;
int nw = 0;
for(int i=0;s1[i] != 0;++i){
nw = ch[nw][s1[i] - 'a'];
if(danger[nw]) flag1[i-w+1] = true;
}
nw = 0;
for(int i=0;s2[i] != 0;++i){
nw = ch[nw][s2[i] - 'a'];
if(danger[nw]) flag2[i-w+1] = true;
}
}
bool vis[maxn];
bool le[maxn],ri[maxn],both[maxn];
#define v G[i].to
inline bool dfs(int u,int f){
using namespace Graph;
using namespace SAM;
for(int i = head[u];i;i=G[i].next){
if(v == f) continue;
if(dfs(v,u)) return true;
if(le[v] && ri[v]) both[u] = true;
else le[u] |= le[v],ri[u] |= ri[v];
}
if(!vis[T[u].x]){
if(T[u].x < len1) le[u] = true;
if(T[u].x > len1) ri[u] = true;
}
if(T[u].len >= mid){
if(le[u] && ri[u]) return true;
if(le[u] && both[u]) return true;
if(ri[u] && both[u]) return true;
}
le[u] |= both[u];ri[u] |= both[u];
return false;
}
#undef v
inline bool check(){
for(int i=len1-1,c=0;i>=0;--i){
vis[i] = false;
if(flag1[i]) c = mid - w + 1;
if(c != 0) vis[i] = true,-- c;
}vis[len1] = true;
for(int i=len2-1,c=0;i>=0;--i){
vis[i+len1+1] = false;
if(flag2[i]) c = mid - w + 1;
if(c != 0) vis[i+len1+1] = true,--c;
}
for(int i=0;i<=SAM::nodecnt;++i) le[i] = ri[i] = both[i] = 0;
if(dfs(0,0)) return true;
return false;
}
int main(){
scanf("%s",s1);scanf("%s",s2);scanf("%s",s3);
ACM::insert(s3);ACM::build();
len1 = strlen(s1);len2 = strlen(s2);w = strlen(s3);
work1();SAM::init();
for(int i=len2-1;i>=0;--i) SAM::insert(s2[i],len1+i+1);SAM::insert('z'+1,len1);
for(int i=len1-1;i>=0;--i) SAM::insert(s1[i],i);
for(int i=1;i<=SAM::nodecnt;++i) Graph::add(SAM::T[i].fa,i);
int l = 0,r = len1,ans = 0;
while(l <= r){
mid = (l+r) >> 1;
if(check()) l = mid+1,ans = mid;
else r = mid-1;
}
printf("%d
",ans);
getchar();getchar();
return 0;
}