AC 로봇 주제 요약

최근에 비교적 바빠서 AC자동기 주제를 겨우 두 주일이 걸려서 미루었다
AC와 결합하는 몇 가지 문제는 다음과 같습니다. 1.AC 로봇 템플릿 문제 잔말 2.AC자동기와 dp를 결합하면 매트릭스와 자주 연결되거나 일부 전이된 예처리(trie 그림)가 있지만 모두 비교적 누드적이다.AC 로봇 더하기 fail 트리 개인 이해 접두사 트리의 접두사 트리
템플릿 문제는 안 할게요.

Problem J

dp문제인 것을 알 수 있지만 꼬치의 길이가 매우 크다는 것을 발견했다. 이런 문제의 일반적인 사고방식은 다음과 같다.먼저 폭력을 쓰다매트릭스 빠른 멱 최적화 매트릭스 A[i][j]는 dp[k][i]가 dp[k][j]에 대한 기여(모든 dp+매트릭스에 적용되는 문제

#include
#include
using namespace std;
// The code is by Zerokei
#define FOR(i,x,y) for(int i=(x),i##_end_=(y);i<=i##_end_;i++)
#define DOR(i,x,y) for(int i=(x),i##_end_=(y);i>=i##_end_;i--)
#define P 100000
int Hash(char c){
    if(c=='A')return 1;
    if(c=='C')return 2;
    if(c=='T')return 3;
    return 0;
}
void Add(int &x,int y){
    x+=y;
    if(x>=P)x-=P;
}
struct Mat{
    int n,m;
    int A[105][105];
    Mat(){memset(A,0,sizeof A);}
    void Clear(){memset(A,0,sizeof A);}
    Mat operator *(const Mat &B){
        Mat res;
        res.n=n;
        FOR(i,0,n)FOR(k,0,n)
        if(A[i][k])FOR(j,0,n){
            Add(res.A[i][j],1ll*A[i][k]*B.A[k][j]%P);
        }
        return res;
    }
    void print(){
        FOR(i,0,n){
            FOR(j,0,n)printf("%d ",A[i][j]);
            puts("");
        }
        puts("");
    }
}S;
struct Aho_Corasick{
    static const int Len=105;
    int pre[Len][4],Q[Len],F[Len],fail[Len];
    int Sum[Len][Len];
    int tot,L,R;
    int newnode(){
        tot++;
        FOR(i,0,3)pre[tot][i]=0;
        fail[tot]=F[tot]=0;
        return tot;
    }
    void init(){
        tot=-1;
        newnode();
    }
    void insert(char *str){
        int len=strlen(str),cur=0;
        FOR(i,0,len-1){
            int k=Hash(str[i]);
            if(!pre[cur][k])pre[cur][k]=newnode();
            cur=pre[cur][k];
        }
        F[cur]=1;
    }
    void build(){
        L=R=0;
        FOR(i,0,3)if(pre[0][i])Q[++R]=pre[0][i];
        while(Lint k=Q[++L];
            F[k]|=F[fail[k]];
            FOR(i,0,3){
                int &p=pre[k][i];
                if(p)fail[p]=pre[fail[k]][i],Q[++R]=p;
                else p=pre[fail[k]][i];
            }
        }
    }
    void Make(){
        S.Clear();
        S.n=tot;
        FOR(i,0,tot)FOR(j,0,3){
            int k=pre[i][j];
            if(!F[k])S.A[i][k]++;
        }
    }
    void DP(int n){
        Mat ans;
        ans.n=tot;
        ans.A[0][0]=1;
        while(n){
            if(n&1)ans=ans*S;
            n>>=1;
            S=S*S;
        }
        int res=0;
        FOR(i,0,tot)Add(res,ans.A[0][i]);
        printf("%d
",res);
    }
}ACA;
char str[15];
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    ACA.init();
    FOR(i,1,m){
        scanf("%s",str);
        ACA.insert(str);
    }
    ACA.build();
    ACA.Make();
    ACA.DP(n);
    return 0;
} 

Problem O

트리+fail 트리+라인 트리fail 트리는 주로 그의 dfs 서열을 이용하여 라인 트리에 []+str와 같은 열을 업데이트한 다음에 트리에str+[]와 같은 열을 매거할 수 있다. 이 두 가지를 결합하면 많은 하위 열에 포함된 문제를 해결할 수 있다. 즉, 자신의 하위 열에서 값을 업데이트하는 것이다.

#include
using namespace std;
#define FOR(i,x,y) for(int i=(x),i##_END_=(y);i<=i##_END_;i++)
#define DOR(i,x,y) for(int i=(x),i##_END_=(y);i>=i##_END_;i--)
#define M 300005
#define N 20005
int Max(int x,int y){return x>y?x:y;}
void chk_mx(int &x,int y){if(xstring str[N];
int len[N],Val[N];
int n;

//dfn
int Lt[M],Rt[M],tta;

//Link
int Head[M],nxt[M],To[M],ttaE;
void addedge(int a,int b){nxt[++ttaE]=Head[a];Head[a]=ttaE;To[ttaE]=b;}
#define LFOR(i,x) for(int i=Head[x];i;i=nxt[i])

struct Segment_Tree{
    #define Lson l,mid,p<<1
    #define Rson mid+1,r,p<<1|1
    struct node{int l,r,mx;}tree[M<<2];
    void build(int l,int r,int p){
        tree[p].l=l,tree[p].r=r,tree[p].mx=0;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(Lson);build(Rson);
    }
    void update(int l,int r,int sum,int p){
        if(tree[p].l==l&&tree[p].r==r){chk_mx(tree[p].mx,sum);return;}
        int mid=(tree[p].l+tree[p].r)>>1;
        if(mid>=r)update(l,r,sum,p<<1);
        else if(mid1|1);
        else update(l,mid,sum,p<<1),update(mid+1,r,sum,p<<1|1);
    }
    int query(int x,int p){
        if(tree[p].l==tree[p].r)return tree[p].mx;
        int mid=(tree[p].l+tree[p].r)>>1;
        if(mid>=x)return Max(tree[p].mx,query(x,p<<1));
        else return Max(tree[p].mx,query(x,p<<1|1));
    }
}Tree;

struct Aho_Carosick{
    int Q[M],pre[M][26],fail[M];
    int L,R,tot;

    int newnode(){
        tot++;
        Head[tot]=fail[tot]=0;
        FOR(i,0,25)pre[tot][i]=0;
        return tot;
    }
    void init(){tot=-1;newnode();}

    void insert(int num){
        cin>>str[num];
        scanf("%d",&Val[num]);
        len[num]=str[num].size();
        int cur=0;
        FOR(i,0,len[num]-1){
            int k=str[num][i]-'a',&p=pre[cur][k];
            if(!p)p=newnode();
            cur=p;
        }
    }
    void build(){
        L=R=0;
        FOR(i,0,25)if(pre[0][i])Q[++R]=pre[0][i];
        while(Lint k=Q[++L];
            addedge(fail[k],k);
            FOR(i,0,25){
                int &p=pre[k][i];
                if(p)Q[++R]=p,fail[p]=pre[fail[k]][i];
                else p=pre[fail[k]][i];
            }
        }
    }
    void dfs(int x){
        Lt[x]=++tta;
        LFOR(i,x)dfs(To[i]);
        Rt[x]=tta;
    }
    void Solve(){
        Tree.build(1,tta,1);
        int ans=0;
        FOR(i,1,n){
            int cur=0,res=0;
            FOR(j,0,len[i]-1){
                int k=str[i][j]-'a';
                cur=pre[cur][k];
                chk_mx(res,Tree.query(Lt[cur],1));
            }
            Tree.update(Lt[cur],Rt[cur],res+Val[i],1);
            chk_mx(ans,res+Val[i]);
        }
        printf("%d
",ans);
    }
}ACA;

void Init(){
    tta=ttaE=0;
    ACA.init();
}
int main(){
    int T;
    scanf("%d",&T);
    FOR(cas,1,T){
        Init();
        scanf("%d",&n);

        FOR(i,1,n)ACA.insert(i);
        ACA.build();
        ACA.dfs(0);

        printf("Case #%d: ",cas);
        ACA.Solve();
    }
    return 0;
}

Problem P

이것은 순수하고 순수한 제목이다. 233은 접두사와 접두사의 결합에 대해 c가 만족하는지 확인하려면 접두사가 a이고 접두사가 b이다. 사실 이렇게 a#b c#c를 구성할 수 있다. 그리고 a#b가 c#c의 자열인지 판단하기만 하면 된다.

#include
using namespace std;
#define FOR(i,x,y) for(int i=(x),i##_END_=(y);i<=i##_END_;i++)
#define DOR(i,x,y) for(int i=(x),i##_END_=(y);i>=i##_END_;i--)
#define M 100005
string S[M];
int pos[M];
struct Aho_Corasick{
    #define N 600005
    int pre[N][27],fail[N],Q[N],dep[N],tmp[N],pass[N];
    int tot,L,R;
    void init(){
        tot=-1;
        newnode();
    }
    int newnode(){
        tot++;
        FOR(i,0,26)pre[tot][i]=0;
        pass[tot]=fail[tot]=tmp[tot]=0;
        return tot;
    }
    void insert(int num){
        char a[N],b[N];
        string c;
        scanf("%s",a);
        scanf("%s",b);
        c+=b;c+='{';c+=a;
        int len=c.size(),cur=0;
        FOR(i,0,len-1){
            int k=c[i]-'a',&p=pre[cur][k];
            if(!p)p=newnode();
            cur=p;
            dep[p]=i;
        }
        pos[num]=cur;
    }
    void Build(){
        L=R=0;
        FOR(i,0,26)if(pre[0][i])Q[++R]=pre[0][i];
        while(Lint k=Q[++L];
            FOR(i,0,26){
                int &p=pre[k][i];
                if(p)Q[++R]=p,fail[p]=pre[fail[k]][i];
                else p=pre[fail[k]][i];
            }
        }
    }
    void Solve(string &str,int num){
        int len=str.size(),cur=0;
        FOR(i,0,len-1){
            cur=pre[cur][str[i]-'a'];
            int now=cur;
            while(now){
                if(tmp[now]==num)break;
                if((len>>1)else pass[now]++,tmp[now]=num;
                now=fail[now];
            }
        }
    }
}ACA;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        ACA.init();
        FOR(i,1,n){
            char s[100005];
            scanf("%s",s);
            S[i]=s;
            S[i]+='{';S[i]+=s;
        }
        FOR(i,1,m)ACA.insert(i);
        ACA.Build();
        FOR(i,1,n)ACA.Solve(S[i],i);
        FOR(i,1,m)printf("%d
",ACA.pass[pos[i]]);
    }
    return 0;
}

그리고 몇 가지 작은 방법과 작은 결론: 1.만약 한 단어가 답안에 한 번 이상 공헌을 한다면, 마크를 직접 표시할 수 있고, -1이면 건너뛸 수 있으며, 이러한 복잡도는 O (len)로 축소된다
2. 여러 문장이 한 사전에 대한 조회와 단어가 한 문장에 가장 많은 기여를 한다면 tmp 수조로 가장 늦은 기여 시간을 기록한 다음while(now)에서 판단하면 된다.
3. 단어가 문장에 여러 번 기여하면 fail 트리를 사용하고 dfs 서해를 할 수 있습니다. 복잡도는 O(len)이지만 코드가 복잡할 수 있습니다.