SHARE
TWEET

LG4112

yicongli Mar 25th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=4007;
  17.  
  18. struct sam{
  19.     int tot;
  20.     int len[N];
  21.     int trans[N][26];
  22.     int fa[N];
  23.  
  24.     inline int NewNode(int mx,int *tr,int su){
  25.         ++tot;
  26.         len[tot]=mx;
  27.         if(tr!=NULL)memcpy(trans[tot],tr,26<<2);
  28.         fa[tot]=su;
  29.         return tot;
  30.     }
  31.  
  32.     inline int Extend(int u,int c){
  33.         int t=NewNode(len[u]+1,NULL,0);
  34.         for(;u&&!trans[u][c];u=fa[u])trans[u][c]=t;
  35.         if(!u){
  36.             fa[t]=1;
  37.             return t;
  38.         }
  39.         int v=trans[u][c];
  40.         if(len[v]==len[u]+1){
  41.             fa[t]=v;
  42.             return t;
  43.         }
  44.         int x=NewNode(len[u]+1,trans[v],fa[v]);
  45.         fa[t]=fa[v]=x;
  46.         for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=x;
  47.         return t;
  48.     }
  49.  
  50.     inline void build(char *s,int n){
  51.         int lst=NewNode(0,NULL,0);
  52.         for(int i=0;i<n;++i){
  53.             lst=Extend(lst,s[i]-'a');
  54.         }
  55.     }
  56. }samA,samB;
  57.  
  58. struct seq{
  59.     int tot;
  60.     int trans[N][26];
  61.     inline void build(char *s,int n){
  62.         tot=n+1;
  63.         for(int i=n-1;~i;--i){
  64.             memcpy(trans[i+1],trans[i+2],26<<2);
  65.             trans[i+1][s[i]-'a']=i+2;
  66.         }
  67.     }
  68. }seqA,seqB;
  69.  
  70. struct DAG{
  71.     int tot;
  72.     int *trans[N];
  73.  
  74.     DAG(sam &a){
  75.         tot=a.tot;
  76.         for(int i=1;i<=tot;++i)trans[i]=a.trans[i];
  77.     }
  78.     DAG(seq &a){
  79.         tot=a.tot;
  80.         for(int i=1;i<=tot;++i)trans[i]=a.trans[i];
  81.     }
  82. };
  83.  
  84. struct Data{
  85.     int a,b,t;
  86. };
  87.  
  88. bool vis[N][N];
  89.  
  90. inline int bfs(DAG A,DAG B){
  91.     for(int i=1;i<=A.tot;++i){
  92.         for(int j=1;j<=B.tot;++j){
  93.             vis[i][j]=0;
  94.         }
  95.     }
  96.     vis[1][1]=1;
  97.     queue<Data>Q;
  98.     Q.push(Data{1,1,0});
  99.     while(!Q.empty()){
  100.         Data t=Q.front();
  101.         Q.pop();
  102.         for(int i=0;i<26;++i){
  103.             int x=A.trans[t.a][i];
  104.             int y=B.trans[t.b][i];
  105.             if(vis[x][y]||!x)continue;
  106.             if(!y)return t.t+1;
  107.             vis[x][y]=1;
  108.             Q.push(Data{x,y,t.t+1});
  109.         }
  110.     }
  111.     return -1;
  112. }
  113.  
  114. char A[N];
  115. char B[N];
  116.  
  117. int main(){
  118.     // freopen(".in","r",stdin);
  119.     // freopen(".out","w",stdout);
  120.     scanf("%s%s",A,B);
  121.     int lenA=strlen(A);
  122.     int lenB=strlen(B);
  123.     samA.build(A,lenA);
  124.     seqA.build(A,lenA);
  125.     samB.build(B,lenB);
  126.     seqB.build(B,lenB);
  127.     printf("%d\n",bfs(samA,samB));
  128.     printf("%d\n",bfs(samA,seqB));
  129.     printf("%d\n",bfs(seqA,samB));
  130.     printf("%d\n",bfs(seqA,seqB));
  131. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top