4032: [HEOI2015]最短不公共子串

题目连接：

Description

在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。

一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。

一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。

下面，给两个小写字母串A，B，请你计算：

(1) A的一个最短的子串，它不是B的子串

(2) A的一个最短的子串，它不是B的子序列

(3) A的一个最短的子序列，它不是B的子串

(4) A的一个最短的子序列，它不是B的子序列

Input

有两行，每行一个小写字母组成的字符串，分别代表A和B。

Output

输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1.

Sample Input

aabbcc

abcabc

Sample Output

2

4

2

4

Hint

对于100%的数据，A和B的长度都不超过2000

题意

题解：

bfs四合一

答案都是最长公共子XX+1

子串我们用后缀自动机去跑，子序列我们用dp的贪心去跑就好了

那个dp表示从i位置走到字符j的最小位置

注意后缀自动机要开两倍空间……因为这个，wa成傻逼了

代码

#include
    
     using namespace std;const int maxn = 2e3+5;char s1[maxn],s2[maxn];int len1,len2;int go1[maxn][26],go2[maxn][26];int vis[maxn][maxn*2];int Son[maxn*2][26],pre[maxn*2],len[maxn*2],la=1,Now=1;struct SAM{    void add(int x)    {        int p=la,np=la=++Now;        len[np]=len[p]+1;        for(;p&&!Son[p][x];p=pre[p])            Son[p][x]=np;        if(!p)            pre[np]=1;        else        {            int q=Son[p][x];            if(len[q]==len[p]+1)                pre[np]=q;            else            {                int nq=++Now;                memcpy(Son[nq],Son[q],sizeof Son[nq]);                len[nq]=len[p]+1;                pre[nq]=pre[q];                pre[q]=pre[np]=nq;                for(;p&&Son[p][x]==q;p=pre[p])                    Son[p][x]=nq;            }        }    }}sam;struct node{    int x,y,l;};queue
     
      Q;void init(){    memset(vis,0,sizeof(vis));    while(!Q.empty())Q.pop();}int solve1(){    init();    for(int i=0;i