bzoj4032 [HEOI2015] 최단 비공식 하위 문자열 (문자열 dp+SAM)

제목 링크
분석: 문자열 dp사합일은 신의 한 문제입니다. 처음에는 첫 번째 질문만 할 줄 알았는데 자신의 방법이 믿음직하지 않다는 것을 발견했습니다.

First.A 문자열≠ B 문자열

실제로 두 열의 가장 긴 공통 서브열 f[i][j]f[i][j]는 A 서열 ii위가 B 서열 jj위와 일치한다는 것을 나타낸다. 가장 긴 공통 서브열 f[i][j]=f[i]=f[i-1][j][j-1]+1(A[i]=B[j])f[i][j]=f[i]=f[i-1][j][j][j]+1(A[i]=B[j])의 답은 모든 가장 긴 공통 서브열 중 가장 작은 값이다.
여기서 주의해야 할 점은 다음과 같습니다.

if (a!=i) ans=min(ans,a+1);

기록된 최대 공통 문자열 길이

왜 a!=ia!=i 때 답안을 업데이트할 수 있을까요?

a==ia==i 때문에 AA 서열 1:i 1:i 비트가 모두 일치한다는 것을 의미한다. 그러면 얻은 답안은 a+1a+1이 의미가 없을 수도 있다(A와 B 서열이 완전히 같을 수도 있고 정답은 -1일 수도 있다)

Second.A 문자열 ≠ B 시퀀스

욕심은 일괄서열 A의 일치점, 욕심의 일치 B서열도 우리는 dp로 f[i][j][j][i][j][j]]를 완성할 수 있다. 매거서열 A의 일치점, 욕심의 일치 B서열은 우리가 dp로 f[i][j][i][j][j]=f[i: [i: 1] [j-1] [j]+1(A[i]=1] [[i]=[[[i]=B[[[j]] [i] [i] [j][[i] [[[[j]] [[j]] [[j][[[[j]]]][[[[[[j]]]]][[[[[[j]]]][[[[[j]]]]]][[[j]]][(A[i]!=B[j]) f[i][j]=f[i][j-3-1](A[i]!=B[j])
왜 같지 않을 때 이렇게 옮겨요?우리가 매거한ii의 A의 하위 문자열은 반드시 연속적이기 때문에ii가 반드시 일치해야 하기 때문에ii는 움직일 수 없습니다
또는 참고:

if (a!=i) ans=min(ans,a+1);

Third.A 하위 시퀀스≠ B 하위 문자열

B열로 SAMSAM 디자인 상태 만들기: l[i]l[i]는 SAMSAM의 결점ii로 A 서열을 매칭하면 얻을 수 있는 가장 짧은 길이를 나타낸다. 우리는 A의 매개ii와 SAMSAMSAM의 매개점 jj가ch[j][i][j]이 매칭하면 매칭할 수 있는 가장 짧은 길이를 나타낸다. 따라서 l[ch[j][i]]]]]=min(l[j]+1)l[ch[j][j][i]]][l[j]]][i]]]][lj][i]]][lj][i]]+1](lj]+1)

Fourth.A 서브시퀀스≠ B 서브시퀀스

세 번째 질문과는 차이가 많지 않지만 둘 다 하위 서열이기 때문에 우리는 하나의 수조 ccc[i][j]c[i][j][j]를 미리 처리해야 한다. B 서열에서 ii위 이전 문자 jj의 최근 위치를 표시한다.
우리는 또한 욕심 많은 생각을 이용하여 l[i]l[i]는 문자열 B의 ii위에 일치하는 가장 짧은 길이의 매거 A의 각 ii, 거꾸로 매거 B의 각 jj(우리가 cc수조를 구성하는 의미에 주의)를 나타낸다. 만약에 c[j][A[i]]]c[j][A[A]]]]라는 결점이 있다면 j가 이전에 A[i]A[i]와 일치할 수 있는 위치가 있었다는 것을 의미한다. 따라서 l[c[j][A[i][i]]]]][l[j]+1][ji][jj][j][jj][j][j]][jj]]][ji][j][j]]]][jj][j][j]]]][jj]][jj]]

tip

하늘만큼 큰 구덩이: if (a!=i) ans=min(ans,a+1);다라오들이 무릎을 꿇고 힘을 내는 걸 보고 한 발씩 했어요.

#include
#include
#include

using namespace std;

const int INF=1e9;
const int N=4005;
int dis[N],ch[N][26],fa[N],last=1,root=1,sz=1,len;
int f[2003][2003],l[N],l1,l2,c[N][26],mp[26];
char s[N],ss[N];

void insert(int x)
{
    int now=++sz,pre=last;
    last=now;
    dis[now]=dis[pre]+1;
    for (;pre&&!ch[pre][x];pre=fa[pre]) ch[pre][x]=now;

    if (!pre) fa[now]=root;
    else
    {
        int q=ch[pre][x];
        if (dis[q]==dis[pre]+1) fa[now]=q;
        else
        {
            int nows=++sz;
            dis[nows]=dis[pre]+1;
            memcpy(ch[nows],ch[q],sizeof(ch[q]));
            fa[nows]=fa[q]; fa[q]=fa[now]=nows;
            for (;pre&&ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
        }
    }
}

void solve1()
{
    memset(f,0,sizeof(f));
    int ans=INF;
    for (int i=1;i<=l1;i++)
    {
        int a=0;
        for (int j=1;j<=l2;j++)
        {
            if (s[i]==ss[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            a=max(a,f[i][j]);
        }
        if (a!=i) ans=min(ans,a+1);    //a!=i 
    }       
    if (ans>l1||ans>l2) printf("-1
");
    else printf("%d
",ans);
}

void solve2()
{
    memset(f,0,sizeof(f));
    int ans=INF;
    for (int i=1;i<=l1;i++)   //     
    {
        int a=0;
        for (int j=1;j<=l2;j++)
        {
            if (s[i]==ss[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            else f[i][j]=f[i][j-1];
            a=max(a,f[i][j]);
        }
        if (a!=i) ans=min(ans,a+1);
    }
    if (ans>l1||ans>l2) printf("-1
");
    else printf("%d
",ans);
}

void solve3()
{
    memset(l,0x33,sizeof(l));
    l[1]=0;
    int ans=INF;
    for (int i=1;i<=l1;i++)
        for (int j=1;j<=sz;j++)
        {
            int t=ch[j][s[i]-'a'];
            if (!t) ans=min(ans,l[j]+1);
            else l[t]=min(l[t],l[j]+1);
            //l     a                ，   i           
        }
    if (ans>l1||ans>l2) printf("-1
");
    else printf("%d
",ans);
}

void solve4()
{
    memset(l,0x33,sizeof(l));
    l[0]=0;
    int ans=INF;
    for (int i=l2;i>=0;i--)
    {
        for (int j=0;j<26;j++)
            if (mp[j]) c[i][j]=mp[j];
        mp[ss[i]-'a']=i;
    }
    for (int i=1;i<=l1;i++)
        for (int j=l2;j>=0;j--)
        {
            int t=c[j][s[i]-'a'];
            if (!t) ans=min(ans,l[j]+1);
            else l[t]=min(l[t],l[j]+1);
        }
    if (ans>l1||ans>l2) printf("-1
");
    else printf("%d
",ans);
}

int main()
{
    scanf("%s",s+1); 
    scanf("%s",ss+1);  len=strlen(ss+1);
    for (int i=1;i<=len;i++) insert(ss[i]-'a');
    l1=strlen(s+1); l2=strlen(ss+1);
    solve1();
    solve2();
    solve3();
    solve4();
    return 0;
}