联训总结 DAY 3

KMP

1.基础

傻逼玩意儿，用AC自动机替代。

2.例题

不可用。

Tire树

1.基础

智障玩意儿。

2.例题 Hdu 1251 统计难题

题意

模板。

解析

学好Tire树。

代码

#include<bits/stdc++.h>
using namespace std;
int trie[1000010][26],num[1000010]={0},pos=1;
void Insert(char word[]){
    int i,c=0;
    for(i=0;word[i];i++){
        int n=word[i]-'a';
        if(trie[c][n]==0)
            trie[c][n]=pos++;
        c=trie[c][n];
        num[c]++;
    }
}
int Find(char word[]){
    int i,c=0;
    for(i=0;word[i];i++){
        int n=word[i]-'a';
        if(trie[c][n]==0)
            return 0;
        c=trie[c][n];
    }
    return num[c];
}
int main(){
    char word[11];
    while(gets(word)){
        if(word[0]==NULL){
            break;
        }
        Insert(word);
    }
    while(gets(word)){
        printf("%d\n",Find(word));
    }
    return 0;
}

AC自动机

1.基础

好东西。

2.例题

A.Luogu 3808 【模板】AC自动机（简单版）

题意

模板。

解析

学好AC自动机。

代码

#include<bits/stdc++.h>
using namespace std;
struct tree{
    int fail,vis[26],end;
}e[1000007];
int cnt;
void ac_build(string s){
    int l=s.length(),now=0;
    for(register int i=0;i<l;i++){
        if(!e[now].vis[s[i]-'a']){
            cnt++;
            e[now].vis[s[i]-'a']=cnt;
        }
        now=e[now].vis[s[i]-'a'];
    }
    e[now].end++;
}
void ac_fail(){
    queue<int> q;
    for(register int i=0;i<26;i++){
        if(e[0].vis[i]){
            e[e[0].vis[i]].fail=0;
            q.push(e[0].vis[i]);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(register int i=0;i<26;i++){
            if(e[u].vis[i]){
                e[e[u].vis[i]].fail=e[e[u].fail].vis[i];
                q.push(e[u].vis[i]);
            }
            else{
                e[u].vis[i]=e[e[u].fail].vis[i];
            }
        }
    }
}
int ac_run(string s){
    int l=l=s.length(),now=0,ans=0;
    for(register int i=0;i<l;i++){
        now=e[now].vis[s[i]-'a'];
        for(register int t=now;t&&e[t].end!=-1;t=e[t].fail){
            ans+=e[t].end;
            e[t].end=-1;
        }
    }
    return ans;
}
int main(){ 
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    for(register int i=1;i<=n;i++){
        cin>>s;
        ac_build(s);
    }
    e[0].fail=0;
    ac_fail();
    cin>>s;
    cout<<ac_run(s);
    return 0;
}

B.Hdu 2222 AC自动机

详情：liu940204的博客

C.Luogu 2444 [POI2000]病毒

题意

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如,如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请判断是否存在一个无限长的安全代码。

解析

首先我们把所有串建一个AC自动机。
方便起见我们直接把fail指针合并到子结点。
如果一个串能无限长,也就是说它可以在AC自动机上一直进行匹配但就是匹配不上。
也就是说匹配指针不能走到val为1的结点,设这个点为x。
即root..x是一个病毒串。
那么fail指针指向x的y也不能走，因为root..x是root..y的一个后缀。
处理出来判断有向图是否有环，dfs即可。

代码

#include<bits/stdc++.h>
#define maxx 30007
using namespace std;
int n;
inline int read(){
    int X=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
struct mca{
    int cnt,next[maxx][2],fail[maxx],danger[maxx],q[maxx];
    bool vis[maxx],ins[maxx];
    char ch[maxx];
    mca(){
        cnt=1;
        for(int i=0;i<2;i++)next[0][i]=1;
    }
    void insert(){
        scanf("%s",ch);
        int now=1,l=strlen(ch);
        for(int i=0;i<l;i++){
            if(!next[now][ch[i]-'0'])next[now][ch[i]-'0']=++cnt;
            now=next[now][ch[i]-'0'];
        }
        danger[now]=1;
    }
    void buildfail(){
        int head=0,tail=1;
        q[0]=1;fail[0]=1;
        while(head!=tail){
            int now=q[head];head++;
            for(int i=0;i<=1;i++){
                int v=next[now][i];
                if(!v){
                    next[now][i]=next[fail[now]][i];
                    continue;
                }
                int k=fail[now];
                while(!next[k][i])k=fail[k];
                fail[v]=next[k][i];
                danger[v]|=danger[next[k][i]];
                q[tail++]=v;
            }
        }
    }
    bool dfs(int x){
        ins[x]=1;
        for(int i=0;i<=1;i++){
            int v=next[x][i];
            if(ins[v])return 1;
            if(vis[v]||danger[v])continue;
            vis[v]=1;
            if(dfs(v))return 1;
        }
        ins[x]=0;
        return 0;
    }
}mca;
int main(){
    n=read();
    for(int i=1;i<=n;i++) mca.insert();
    mca.buildfail();
    if(mca.dfs(1))puts("TAK");
    else puts("NIE");
    return 0;
}