【题目描述】：
     在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。
    一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。
    一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。
    下面，给两个小写字母串A，B，请你计算：
    (1) A的一个最短的子串，它不是B的子串
    (2) A的一个最短的子串，它不是B的子序列
    (3) A的一个最短的子序列，它不是B的子串
    (4) A的一个最短的子序列，它不是B的子序列
【题目解法】：
    首先预处理出B串的后缀自动机
    然后预处理出next[i][j]表示第i位后面第一次出现j的位置，对A B各求出一个nextA nextB
    Task1：显然我们枚举A中子串的开头，然后再后缀自动机上匹配即可，一旦发现失配那么用当前长度+1更新最小答案
    Task2：显然我们继续枚举A中子串的开头，然后我们贪心的用nextB来进行匹配，同理一旦发现失配那么用当前长度+1更新最小答案
    Task3：我们用f[i][j]表示A串匹配到第i位，后缀自动机上的第j位的最短长度。枚举i和j的上一位设为k，然后j=tree[k].son[a[i]]，然后更新用f[t][k]更新f[i][j]，其中t<i，因此我们用个一位数组即可保存f[1..i-1][j]的最小值，一旦发现失配那么用当前长度+1更新最小答案
    Task4：与Task3类似，只不过我们不再后缀自动机上找，我们贪心的在nextB上面找下一位即可
    总的复杂度为O(N^2)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=4005;
const int M=27;
const int INF=32083208;
struct SamNode {int son[M],fa,len;} tree[N]; int tot,tail;
int n,m,a[N],b[N],nextA[N][M],nextB[N][M],last[N],f[N],ans;
inline void getString(int a[],int &n)
{
    char s[N];
    scanf("%s",s+1); n=strlen(s+1);
    for (int i=1; i<=n; i++) a[i]=s[i]-'a'+1;
}
void CalcNext()
{
    for (int i=1; i<=26; i++) last[i]=n+1;
    for (int i=n; i>=0; i--)
    {
        for (int j=1; j<=26; j++) nextA[i][j]=last[j];
        last[a[i]]=i;
    }
    for (int i=1; i<=26; i++) last[i]=n+1;
    for (int i=m; i>=0; i--)
    {
        for (int j=1; j<=26; j++) nextB[i][j]=last[j];
        last[b[i]]=i;
    }
}
inline void add(int c)
{
    int np=++tot,p=tail; tail=np; tree[np].len=tree[p].len+1;
    for (;p&&(tree[p].son[c]==0);p=tree[p].fa) tree[p].son[c]=np;
    if (p==0) {tree[np].fa=1; return;} int q=tree[p].son[c];
    if (tree[q].len==tree[p].len+1) {tree[np].fa=q; return;}
    int nq=++tot; tree[nq]=tree[q]; tree[nq].len=tree[p].len+1;
    tree[np].fa=tree[q].fa=nq;
    for (;p&&(tree[p].son[c]==q);p=tree[p].fa) tree[p].son[c]=nq;
}
void init()
{
    getString(a,n); getString(b,m); CalcNext();
    tot=tail=1; for (int i=1; i<=m; i++) add(b[i]);
}
void solve()
{
    ans=INF;
    for (int i=1; i<=n; i++)
    {
        int now=1,len=0;
        for (int j=i; j<=n; j++)
        {
            if (tree[now].son[a[j]]==0) {ans=min(ans,len+1); break;}
            len++; now=tree[now].son[a[j]];
        }
    }
    if (ans>n) printf("%d\n",-1); else printf("%d\n",ans);
    ans=INF;
    for (int i=1; i<=n; i++)
    {
        int now=0,len=0;
        for (int j=i; j<=n; j++)
        {
            if (nextB[now][a[j]]>n) {ans=min(ans,len+1); break;}
            len++; now=nextB[now][a[j]];
        }
    }
    if (ans>n) printf("%d\n",-1); else printf("%d\n",ans);
    memset(f,127,sizeof(f)); ans=f[0]; f[1]=0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=tot; j++)
        {
            int now=tree[j].son[a[i]];
            if (now==0) ans=min(ans,f[j]+1);
            else f[now]=min(f[now],f[j]+1);
        }
    if (ans>n) printf("%d\n",-1); else printf("%d\n",ans);
    memset(f,127,sizeof(f)); ans=f[0]; f[0]=0;
    for (int i=1; i<=n; i++)
        for (int j=n; j>=0; j--)
        {
            int now=nextB[j][a[i]];
            if (now==n+1) ans=min(ans,f[j]+1);
            else f[now]=min(f[now],f[j]+1);
        }
    if (ans>n) printf("%d\n",-1); else printf("%d\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}