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 条评论

发表评论

邮箱地址不会被公开。