I. Match & Catch
题意:求两个字符串中,在两串中都只出现过一次的最小长度的子串,输出这个最小长度。
分析:把两个串中间用'#'连接起来,创建后缀数组和Height数组,然后扫描Height,需满足:
1.Height[i-1]<Height[i]
2.Height[i+1]<Height[i]
3.在满足1,2的情况下,考虑答案max{Height[i-1],Height[i+1]}+1.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e4+5;
typedef struct SA{
int SA[maxn],Rank[maxn],tp[maxn],tax[maxn],Height[maxn];
int n,m,n1;
char s[maxn];
void build(){
m = 130;
n = strlen(s+1);
GetSA(Rank,tp);
GetHeight();
}
void GetSA(int a[],int b[]);
void RSort(int a[],int b[]);
void GetHeight();
int check(int i);
}SA;
SA a;
int ans;
int main(){
scanf ("%s",a.s+1); a.n1 = strlen(a.s+1);
a.s[a.n1+1] = '#';
scanf ("%s",a.s+a.n1+2);
a.build();
ans = maxn;
for (int i=1;i<=a.n;i++)
if (a.Height[i-1]<a.Height[i] && a.Height[i+1]<a.Height[i] && ((a.SA[i]<=a.n1 && a.SA[i-1]>=a.n1+2) || (a.SA[i-1]<=a.n1 && a.SA[i]>=a.n1+2)))
ans = min(ans,max(a.Height[i-1],a.Height[i+1])+1);
if (ans==maxn) printf ("-1\n");
else printf ("%d\n",ans);
return 0;
}
void SA::GetHeight(){
int j,k=0;
for (int i=1;i<=n;i++){
if (k) k--;
j = SA[Rank[i]-1];
while (s[i+k]==s[j+k]) k++;
Height[Rank[i]] = k;
}
return;
}
void SA::GetSA(int a[],int b[]){
for (int i=1;i<=n;i++) a[i] = s[i],b[i] = i;
RSort(a,b);
int p=0,k=1;
for (;p!=n;k<<=1,m=p){
p = 0;
for (int i=n+1-k;i<=n;i++) b[++p] = i;
for (int i=1;i<=n;i++) if (SA[i]>k) b[++p] = SA[i]-k;
RSort(a,b); swap(a,b);
a[SA[1]] = p = 1;
for (int i=2;i<=n;i++)
a[SA[i]] = (b[SA[i]]==b[SA[i-1]] && b[SA[i]+k]==b[SA[i-1]+k])?p:++p;
}
for (int i=1;i<=n;i++) Rank[SA[i]] = i; //这一步!因为GetSA函数只能保证SA数组完全正确,在赋值完成后最好在给Rank数组再赋一次值
return;
}
void SA::RSort(int a[],int b[]){
for (int i=1;i<=m;i++) tax[i] = 0;
for (int i=1;i<=n;i++) tax[a[b[i]]]++;
for (int i=1;i<=m;i++) tax[i] += tax[i-1];
for (int i=n;i>=1;i--) SA[tax[a[b[i]]]--] = b[i];
return;
}
0 条评论