2019/5/12 day1 解题日志

字数统计: 2.8k字   |   阅读时长: 15分

day1

题目链接

有长度2000的字符串$A$和$B$；
求最短$A$的子串$AA$，使得$AA$不是$B$的子串；
求最短$A$的子串$AA$，使得$AA$不是$B$的子序列；
求最短$A$的子序列$AA$，使得$AA$不是$B$的子串；
求最短$A$的子序列$AA$，使得$AA$不是$B$的子序列；

求最短$A$的子串$AA$，使得$AA$不是$B$的子串

hash + 二分

首先对$A$和$B$串进行$hash$，然后二分答案$ans$，对长度为$ans$的子串$AA$进行枚举，然后到$B$去查询，复杂度$O(n^2logn)$。
由于$hash$用得熟透了，这里就不写了。

后缀数组

对字符串$S = AB$进行后缀排序，中间插入一个$dollor$符号。
那么，要满足$AA$既是$A$的子串，又不是$B$的子串，不妨对所有$A$的后缀$suf_{i}$进行判断：

  • 排名比$suf_{i}$小，且最接近$suf_{i}$的$B$的后缀$suf_{j}$
  • 排名比$suf_{i}$大，且最接近$suf_{i}$的$B$的后缀$suf_{k}$
    容易知道，对于$suf_{i}$而言，对答案的贡献是$max(lcp(suf_i,suf_j) , lcp(suf_i,suf_k))+1$。且要特判这个长度完全在$A$范围内。
    在这个时候，$AA$跟$B$的任何后缀的$LCP$都不会是$AA$。
    时间复杂度$O(n^2)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
const int inf  = 1e9+7;
const int maxn = 4e3+10;
char a[maxn],b[maxn];
int lena,lenb;

int rk[maxn],sa[maxn],height[maxn];
int t1[maxn],t2[maxn],c[maxn];
bool cmp(int *s,int a,int b,int l){
    return s[a]==s[b]&&s[a+l]==s[b+l];
}
void Sa(char *s,int n,int m){
    n++;
    int i,j,p,*x=t1,*y=t2;
    for( i=0;i<m;i++)c[i]=0;
    for( i=0;i<n;i++)c[x[i]=s[i]]++;
    for( i=1;i<m;i++)c[i]+=c[i-1];
    for( i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for( j=1;j<=n;j<<=1){
        p=0;
        for( i=n-j;i<n;i++)y[p++]=i;
        for( i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for( i=0;i<m;i++)c[i]=0;
        for( i=0;i<n;i++)c[x[y[i]]]++;
        for( i=1;i<m;i++)c[i]+=c[i-1];
        for( i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for( i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
        if(p>=n)break;
        m=p;
    }
    int k=0;
    n--;
    for( i=0;i<=n;i++)rk[sa[i]]=i;
    for( i=0;i<n;i++){
        if(k)k--;
        j=sa[rk[i]-1];
        while(s[i+k]==s[j+k])k++;
        height[rk[i]]=k;
    }
}

int solve1(){
    char s[maxn*2];
    int n=0;
    for(int i=0;i<lena;i++)s[n++]=a[i];
    s[n++]='$';
    for(int i=0;i<lenb;i++)s[n++]=b[i];
    s[n]=0;
    Sa(s,n,128);
    int ret=1e7;
    for(int i=1;i<=n;i++){
        if(sa[i]<lena){
            int q1=inf,q2=inf;
            for(int j=i-1;j;j--){
                q1=min(q1,height[j+1]);
                if(sa[j]>lena)break;
            }
            for(int j=i+1;j<=n;j++){
                q2=min(q2,height[j]);
                if(sa[j]>lena)break;
            }
            if(q2==inf)q2=0;
            q1=max(q1,q2);
            if(sa[i]+q1<lena)
            ret=min(ret,q1+1);
        }
    }
    if(ret>maxn)return -1;
    return ret;
}

后缀自动机+bfs

不妨对$A$串和$B$串分别构建一个$SAM$，然后再进行$bfs$，状态为{posa,posb,step}，表示A串走到的状态，B串走到的状态以及当前步数（也就是最短长度）。我们知道$SAM$走出的任一路径都是一个子串，如果A串能够通过字符c走到下一个状态，而此时B串无法通过字符c走到下一个状态，说明找到答案。
由于自动机的$SIZE$是$O(n)$的，所以搜索时的状态数不会超过$O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct SAM{
    int pa[maxn<<1],son[maxn<<1][27];
    int deep[maxn<<1],cnt,root,last;
    inline int newnode(int _deep){
        deep[++cnt]=_deep;
        return cnt;
    }
    inline void sam(int alp){
        int np=newnode(deep[last]+1);
        int u=last;
        memset(son[np],0,sizeof son[np]);
        while(u&&!son[u][alp])son[u][alp]=np,u=pa[u];
        if(!u)pa[np]=root;
        else{
            int v=son[u][alp];
            if(deep[v]==deep[u]+1)pa[np]=v;
            else{
                int nv=newnode(deep[u]+1);
                memcpy(son[nv],son[v],sizeof son[v]);
                pa[nv]=pa[v],pa[v]=pa[np]=nv;
                while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u];
            }
        }last=np;
    }
    inline void pre(){
        cnt=0;
        memset(son[1],0,sizeof son[1]);
        root=last=newnode(0);
    }
}A,B;


int solve1(){
    int ret=inf;
    for(int i=0;i<lena;i++){
        int pos=B.root;
        for(int j=i;j<lena;j++){
            if(B.son[pos][a[j]-'a'])pos=B.son[pos][a[j]-'a'];
            else ret=min(ret,j-i+1);
        }
    }
    if(ret==inf)ret=-1;
    return ret;
}

求最短$A$的子串$AA$，使得$AA$不是$B$的子序列

序列自动机 + 二分

首先构造$B$串的序列自动机，然后二分答案$ans$，再通过暴力判断。二分答案是$O(logn)$的，枚举A串的长度为$ans$的子串是$O(n)$的，暴力判断是$O(n)$的，所以复杂度是$O(n^2logn)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int solve2(){
    int nxt[maxn][26];
    for(int i=0;i<26;i++)nxt[lenb][i]=lenb;
    for(int i=lenb-1;i>=0;i--){
        memcpy(nxt[i],nxt[i+1],sizeof nxt[i+1]);
        nxt[i][b[i]-'a']=i;
    }
    int low=0,high=lena+1;
    while(high-low>1){
        int mid=low+high>>1;
        bool ok=0;
        for(int bg=0;bg+mid-1<lena;bg++){
            int pos=0;
            int i=bg;
            while(i<bg+mid){
                pos=nxt[pos][a[i]-'a'];
                if(pos==lenb){ok=1;break;}
                i++;pos++;
            }
            if(ok)break;
        }
        if(ok)high=mid;
        else low=mid;
    }
    if(high==lena+1)return -1;
    return high;
}

序列自动机

通过上文继续思考，可以发现，其实我们只需要枚举$A$串的起点，然后不断地开始添加连续的字符，假设$ j<k $而$a[i..j]$不满足，那么a[i..k]肯定也不满足，所以到达j时可以剪枝（虽然理论复杂度不变）。
那么就可以直接省去一个二分的复杂度了。

  • 做此类题目不妨先想一想容易想的做法，然后试着去优化复杂度。

后缀自动机 + 序列自动机 + bfs

通过这里我们发现，序列自动机可以通用的处理“子序列”的问题。
首先构造A的SAM和B的序列自动机，然后如上的bfs便可。
显然复杂度也是$O(n^2)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct SEM{
    int nxt[maxn][26];
    int len;
    inline void init(char *s,int l){
        len=l;
        for(int i=0;i<26;i++)nxt[len][i]=len;
        for(int i=len-1;i>=0;i--){
            memcpy(nxt[i],nxt[i+1],sizeof nxt[i+1]);
            nxt[i][s[i]-'a']=i;
        }
    }
}AA,BB;
int solve2(){
    int ret=inf;
    for(int i=0;i<lena;i++){
        int pos=0;
        for(int j=i;j<lena;j++){
            if(BB.nxt[pos][a[j]-'a']==BB.len){
                ret=min(ret,j-i+1);break;
            } else pos=BB.nxt[pos][a[j]-'a']+1;
        }
    }return ret==inf?-1:ret;
}

求最短$A$的子序列$AA$，使得$AA$不是$B$的子串

除了后缀自动机 + 序列自动机 + bfs的做法，还可以DP。

令$dp[i]$表示状态$i$能够接受的最短子序列长度。
如果对于字符$c$，$son[i][c]$存在，则$dp[son[i][c]]=min(dp[i]+1,dp[son[i][c]])$，
否则$ ans=min(ans , dp[i]+1) $

1
2
3
4
5
6
7
8
9
10
11
12
13
int solve3(){
    int ret=inf;
    int dp[maxn];//dp[i]表示状态i能够接受的最短A的子序列
    memset(dp,0x3f,sizeof dp);
    dp[1]=0;
    for(int i=0;i<lena;i++){
        for(int j=B.root;j<=B.cnt;j++){
            if(B.son[j][a[i]-'a']){
                dp[B.son[j][a[i]-'a']]=min(dp[B.son[j][a[i]-'a']],dp[j]+1);
            } else ret=min(ret,dp[j]+1);
        }
    }return ret==inf?-1:ret;
}

求最短$A$的子序列$AA$，使得$AA$不是$B$的子序列

除了序列自动机 + 序列自动机 + bfs的做法，还可以DP，同上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct node{
    int a,b,step;
    node(int a=0,int b=0,int step=0):a(a),b(b),step(step){}
};
bool vis[maxn][maxn]={0};
int solve4(){
    queue<node> q;
    q.push(node(0,0,0));
    while(!q.empty()){
        node now=q.front();q.pop();
        //cout<<now.a<<" "<<now.b<<" "<<now.step<<endl;
        for(int i=0;i<26;i++){
            if(AA.nxt[now.a][i]==AA.len)continue;
            if(vis[AA.nxt[now.a][i]][BB.nxt[now.b][i]])continue;
            if(BB.nxt[now.b][i]==BB.len)return now.step+1;
            vis[AA.nxt[now.a][i]][BB.nxt[now.b][i]]=1;
            q.push(node(AA.nxt[now.a][i]+1,BB.nxt[now.b][i]+1,now.step+1));
        }
    }return -1;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf  = 0x3f3f3f3f;
const int maxn = 4e3+10;
char a[maxn],b[maxn];
int lena,lenb;

struct SEM{
    int nxt[maxn][26];
    int len;
    inline void init(char *s,int l){
        len=l;
        for(int i=0;i<26;i++)nxt[len][i]=len;
        for(int i=len-1;i>=0;i--){
            memcpy(nxt[i],nxt[i+1],sizeof nxt[i+1]);
            nxt[i][s[i]-'a']=i;
        }
    }
}AA,BB;

struct SAM{
    int pa[maxn<<1],son[maxn<<1][27];
    int deep[maxn<<1],cnt,root,last;
    inline int newnode(int _deep){
        deep[++cnt]=_deep;
        return cnt;
    }
    inline void sam(int alp){
        int np=newnode(deep[last]+1);
        int u=last;
        memset(son[np],0,sizeof son[np]);
        while(u&&!son[u][alp])son[u][alp]=np,u=pa[u];
        if(!u)pa[np]=root;
        else{
            int v=son[u][alp];
            if(deep[v]==deep[u]+1)pa[np]=v;
            else{
                int nv=newnode(deep[u]+1);
                memcpy(son[nv],son[v],sizeof son[v]);
                pa[nv]=pa[v],pa[v]=pa[np]=nv;
                while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u];
            }
        }last=np;
    }
    inline void pre(){
        cnt=0;
        memset(son[1],0,sizeof son[1]);
        root=last=newnode(0);
    }
}A,B;


int solve1(){
    int ret=inf;
    for(int i=0;i<lena;i++){
        int pos=B.root;
        for(int j=i;j<lena;j++){
            if(B.son[pos][a[j]-'a'])pos=B.son[pos][a[j]-'a'];
            else{
                ret=min(ret,j-i+1);break;
            }
        }
    }return ret==inf?-1:ret;
}

int solve2(){
    int ret=inf;
    for(int i=0;i<lena;i++){
        int pos=0;
        for(int j=i;j<lena;j++){
            if(BB.nxt[pos][a[j]-'a']==BB.len){
                ret=min(ret,j-i+1);break;
            } else pos=BB.nxt[pos][a[j]-'a']+1;
        }
    }return ret==inf?-1:ret;
}

int solve3(){
    int ret=inf;
    int dp[maxn];//dp[i]表示状态i能够接受的最短A的子序列
    memset(dp,0x3f,sizeof dp);
    dp[1]=0;
    for(int i=0;i<lena;i++){
        for(int j=B.root;j<=B.cnt;j++){
            if(B.son[j][a[i]-'a']){
                dp[B.son[j][a[i]-'a']]=min(dp[B.son[j][a[i]-'a']],dp[j]+1);
            } else ret=min(ret,dp[j]+1);
        }
    }return ret==inf?-1:ret;
}
struct node{
    int a,b,step;
    node(int a=0,int b=0,int step=0):a(a),b(b),step(step){}
};
bool vis[maxn][maxn]={0};
int solve4(){
    queue<node> q;
    q.push(node(0,0,0));
    while(!q.empty()){
        node now=q.front();q.pop();
        //cout<<now.a<<" "<<now.b<<" "<<now.step<<endl;
        for(int i=0;i<26;i++){
            if(AA.nxt[now.a][i]==AA.len)continue;
            if(vis[AA.nxt[now.a][i]][BB.nxt[now.b][i]])continue;
            if(BB.nxt[now.b][i]==BB.len)return now.step+1;
            vis[AA.nxt[now.a][i]][BB.nxt[now.b][i]]=1;
            q.push(node(AA.nxt[now.a][i]+1,BB.nxt[now.b][i]+1,now.step+1));
        }
    }return -1;
}

int main(){
    scanf("%s%s",a,b);
    lena=strlen(a);
    lenb=strlen(b);
    A.pre();B.pre();
    for(int i=0;i<lena;i++)A.sam(a[i]-'a');
    for(int i=0;i<lenb;i++)B.sam(b[i]-'a');
    AA.init(a,lena);BB.init(b,lenb);
    printf("%d\n",solve1());
    printf("%d\n",solve2());
    printf("%d\n",solve3());
    printf("%d\n",solve4());
    return 0;
}

赏

谢谢打赏

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

iOS Developer, ACMer, ...