Description
求两个字符串 (S,T) 的模糊最长公共子串,其中模糊定义为最多有一个字符不同。
Solution
若枚举不同字符在两串中的位置,则有
[ans=max_{i,j} (lcs(i-1,j-1)+lcp(i+1,j+1))+1
]
其中 (lcs(i,j)) 是 (S[1..i]) 和 (T[1..j]) 的最长公共后缀,(lcp(i,j)) 是 (S[i..|S|]) 和 (T[j..|T|]) 的最长公共前缀
稍作变换,得
[ans=max_{i,j} (lcs(i-2,j-2)+lcp(i,j))+1
]
考虑对 (lcp(i,j)) 一项进行枚举,在正向后缀数组中,将 (lcp(i,j)ge k) 的都合并成一段,对于每一段维护其所有 (i) 对应的 (i-2) 的集合,集合内元素按照对应的反向后缀排名排序
于是在对集合进行启发式合并时,我们只需要找到前驱后继并更新答案即可
注意要分别对属于 (S,T) 串的位置进行维护,在计算贡献时,如果当前位置是属于 (S) 的,那么只算 (T) 中的前驱后继对它的贡献,反之亦然
另外,以上计算出的是限制 (lcs,lcp>0) 的情况,即模糊位置处于最终匹配串的中间的情况。因此,对于模糊位置处于匹配串两端的情况,还需要单独讨论处理
(能咬牙把这个题写出来也挺感动的吧,虽然写了 5k 多)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000005;
struct sa
{
struct st
{
int a[N][21];
void build(int *src,int n)
{
for(int i=1; i<=n; i++) a[i][0]=src[i];
for(int i=1; i<=20; i++)
for(int j=1; j<=n-(1<<i)+1; j++)
a[j][i]=min(a[j][i-1],a[j+(1<<(i-1))][i-1]);
}
int query(int l,int r)
{
int j=log2(r-l+1);
return min(a[l][j],a[r-(1<<j)+1][j]);
}
} rmq;
int n,m=256,sa[N],y[N],u[N],v[N],o[N],r[N],h[N],T;
char str[N];
long long ans;
void presolve(string _str)
{
for(int i=1; i<=_str.length(); i++) str[i]=_str[i-1];
n=strlen(str+1);
for(int i=1; i<=n; i++) u[str[i]]++;
for(int i=1; i<=m; i++) u[i]+=u[i-1];
for(int i=n; i>=1; i--) sa[u[str[i]]--]=i;
r[sa[1]]=1;
for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for(int l=1; r[sa[n]]<n; l<<=1)
{
memset(u,0,sizeof u);
memset(v,0,sizeof v);
memcpy(o,r,sizeof r);
for(int i=1; i<=n; i++) u[r[i]]++, v[r[i+l]]++;
for(int i=1; i<=n; i++) u[i]+=u[i-1], v[i]+=v[i-1];
for(int i=n; i>=1; i--) y[v[r[i+l]]--]=i;
for(int i=n; i>=1; i--) sa[u[r[y[i]]]--]=y[i];
r[sa[1]]=1;
for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+((o[sa[i]]!=o[sa[i-1]])||(o[sa[i]+l]!=o[sa[i-1]+l]));
}
{
int i,j,k=0;
for(int i=1; i<=n; h[r[i++]]=k)
for(k?k--:0,j=sa[r[i]-1]; str[i+k]==str[j+k]; k++);
}
rmq.build(h,n);
}
int query(int p,int q)
{
if(p==q) return n-p+1;
p=r[p];
q=r[q];
if(p>q) swap(p,q);
return min(min(n-p+1,n-q+1),rmq.query(p+1,q));
}
};
string str1,str2,str;
sa sa1,sa2;
int belong(int i)
{
if(i<=str1.length()) return 1;
if(i==str1.length()+1) return 0;
return 2;
}
int tosrc(int i)
{
int b=belong(i);
if(b==0) return 0;
if(b==1) return i;
return b-str1.length()-1;
}
int belong2(int i)
{
if(i<=str2.length()) return 1;
if(i==str2.length()+1) return 0;
return 2;
}
int tosrc2(int i)
{
int b=belong(i);
if(b==0) return 0;
if(b==1) return i;
return b-str2.length()-1;
}
int getlcp(int i,int j) // using index in [str]
{
if(belong(i)==belong(j)) return -1e9;
return sa1.query(i,j);
}
int getlcs(int i,int j) // using index in [str]
{
return sa2.query(str.length()-i+1,str.length()-j+1);
}
struct cls_dsu
{
int fa[N];
void init(int n)
{
for(int i=1; i<=n; i++) fa[i]=i;
}
int find(int x)
{
return fa[x]==x ? x : fa[x]=find(fa[x]);
}
} dsu;
int ans=0;
vector <int> vec[N];
int g_lcp=0;
class scorer
{
public:
bool operator ()(const int &e1,const int &e2)
{
return sa2.r[str.length()-e1+1]<sa2.r[str.length()-e2+1];
}
};
void update(int x,int y)
{
int lcs=getlcs(x,y);
int lcp=getlcp(x+2,y+2);
if(lcp<g_lcp) return;
int tmp=lcs+g_lcp+1;
if(tmp>=ans)
{
ans=tmp;
}
}
struct setbox
{
set <int,scorer> *s1,*s2;
setbox()
{
s1=new set<int,scorer>;
s2=new set<int,scorer>;
}
void insert(int x)
{
if(belong(x)==1)
{
set<int,scorer>::iterator it=s2->lower_bound(x);
if(it!=s2->end())
{
update(x,*it);
}
if(it!=s2->begin()) --it;
if(it!=s2->end())
{
update(x,*it);
}
}
if(belong(x)==2)
{
set<int,scorer>::iterator it=s1->lower_bound(x);
if(it!=s1->end())
{
update(*it,x);
}
if(it!=s1->begin()) --it;
if(it!=s1->end())
{
update(*it,x);
}
}
if(belong(x)==1) s1->insert(x);
if(belong(x)==2) s2->insert(x);
}
void mergefrom(set<int,scorer> &src)
{
for(auto i:src)
{
insert(i);
}
}
void mergefrom(setbox &src)
{
mergefrom(*src.s1);
mergefrom(*src.s2);
}
int size()
{
return s1->size()+s2->size();
}
} sb[N];
void do_merge(int i,int j)
{
i=dsu.find(i);
j=dsu.find(j);
if(i==j) return;
if(sb[i].size()<sb[j].size())
{
sb[j].mergefrom(sb[i]);
dsu.fa[i]=j;
}
else
{
sb[i].mergefrom(sb[j]);
dsu.fa[j]=i;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin>>str1>>str2;
str=str1+'$'+str2;
sa1.presolve(str);
reverse(str.begin(),str.end());
sa2.presolve(str);
reverse(str.begin(),str.end());
dsu.init(str.length());
for(int i=2; i<=str.length(); i++)
{
vec[sa1.h[i]].push_back(i);
}
for(int i=3; i<=str.length(); i++)
{
sb[i].insert(i-2);
}
for(int i=str.length(); i>=1; --i)
{
g_lcp=i;
for(auto pos:vec[i])
{
do_merge(sa1.sa[pos-1],sa1.sa[pos]);
}
}
cout<<ans<<endl;
}