LG4762 Virus synthesis

Virus synthesis

처음에는 빈 문자열이 있었는데, 아래의 조작을 이용하여 주어진 문자열 S를 구성했다.

열의 시작 또는 끝에 문자

를 붙인다

열의 시작 또는 끝에 이 열의 역열을 추가

작업 수를 최소화 하십시오.\S\≤105.

문제풀이

분명히 조작 2, 뒤집기 복사를 많이 사용해야 한다.
S의 메모 자동기를 구축하고 dp(i)를 설정하면 구조 노드 i가 메모 문자열에 필요한 최소 조작 횟수를 나타낸다.
ans=min {dp(i)+n-leni}
만약 i가 j로 옮길 수 있다면 dp(j)=dp(i)+1.i는 회문열이기 때문에 i는 반드시 뒤집어서 복제한 것이다.그 전에 j의 문자를 붙이는 것이 바로 이 이동의 의미이다.
회문 자동기가half를 유지하면 dp(i)=dp(halfi)+leni/2-lenhalfi+1.이 전환의 의의는 매우 뚜렷하다.
리턴 로봇이 필요한 DAG의 업데이트 순서를 전송하기 위해 대기열 유지보수를 사용합니다.
시간 복잡성\(O(|S|)\)

#include
using namespace std;
template T read(){
    T x=0,w=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*w;
}
template T read(T&x){
    return x=read();
}
#define co const
#define il inline
typedef long long LL;

co int N=100000+10;
char s[N];
il int idx(char c){
    switch(c){
        case 'A':return 0;
        case 'G':return 1;
        case 'C':return 2;
        default:return 3;
    }
}

int last,tot;
int ch[N][4],fa[N],len[N],half[N];

int get_fa(int x,int i){
    while(s[i-len[x]-1]!=s[i]) x=fa[x];
    return x;
}
void extend(int i){
    int p=get_fa(last,i);
    int x=ch[p][idx(s[i])];
    if(!x){
        x=++tot,memset(ch[x],0,sizeof ch[x]);
        fa[x]=ch[get_fa(fa[p],i)][idx(s[i])];
        len[x]=len[p]+2;
        ch[p][idx(s[i])]=x;
        if(len[x]==1) half[x]=0;
        else{
            int q=half[p];
            while(s[i-len[q]-1]!=s[i]||(len[q]+2)<<1>len[x]) q=fa[q];
            half[x]=ch[q][idx(s[i])];
        }
    }
    last=x;
}

int dp[N];
void real_main(){
    last=tot=1;
    memset(ch[0],0,sizeof ch[0]),memset(ch[1],0,sizeof ch[1]);
    fa[0]=fa[1]=1,len[1]=-1;
    
    scanf("%s",s+1);int n=strlen(s+1);
    for(int i=1;i<=n;++i) extend(i);
    
    dp[0]=1;
    for(int i=2;i<=tot;++i) dp[i]=len[i];
    deque q(1,0);
    int ans=n;
    while(q.size()){
        int p=q.front();q.pop_front();
        for(int c=0;c<4;++c){
            int x=ch[p][c];
            if(!x) continue;
            dp[x]=dp[p]+1;
            int y=half[x];
            dp[x]=min(dp[x],dp[y]+(len[x]>>1)-len[y]+1);
            ans=min(ans,dp[x]+n-len[x]);
            q.push_back(x);
        }
    }
    printf("%d
",ans);
}
int main(){
    for(int T=read();T--;) real_main();
    return 0;
}