字典树哇 AC自动机哇 = _ =

例题 HDU 1251 统计难题

解题思路 :

字典树 原理:按照每个根向下发散 形成一棵 树
这个题 需要在每一个字母处都做统计 (求前缀单词)
开一个 二维数组和ant来 模拟树 root开始为0 作为 起点 t=str[i]-'a'; 作为分支
关键就是 ant 这是形成树的关键 ant用来区分每一个节点 这样二维数组 tree才能
真正构建完成(很神奇....)

代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
int tree[maxn][26]; 构建父子关系
int cnt=0;//节点区分
int root;
int sum[maxn]={0};//统计数组
void insert(char s[]){
    int t;
    root=0;//必须起点为0 来表示树的开始
    for(int i=0;s[i];i++){
        t=s[i]-'a';//转化 数字 便于二维数组 模拟
        if(!tree[root][t]) tree[root][t]=++cnt;
        //节点构建成真实 不同数值便于区分
        sum[tree[root][t]]++;//统计每一(节点/字母)
        root=tree[root][t];//子节点变成父节点
    }
}
int find(char s[]){
    int t;
    root=0;
    for(int i=0;s[i];i++){
        t=s[i]-'a';
        if(!tree[root][t])
        return 0;
        root=tree[root][t];
    }
    return sum[root];
}
int main()
{
    char s[maxn],ask[maxn];
    while(1){
        gets(s);
        if(s[0]=='\0')
        break;
        else
        insert(s);//构树函数
    }
    while(cin>>ask){//查询函数
        cout<<find(ask)<<endl;
    }
     return 0;
}

例题 HDU - 4825 Xor Sum

解题思路及注意事项:

依旧是字典树 按照 0/1建树 不过是从尾部往前找 (因为2进制)
查询时 因为 求异或最大值所以 要求二进制对应每位应该不同
(建树 数组 应该开 要求的样例*13+ 不知道怎么求得的13+)我直接乘了32
具体解析 嵌入代码中了

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<math.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+7;
int a[maxn],b[maxn];
int tree[maxn*32][2]; //构建父子关系
int cnt;//节点区分
int root;
void init()
{
    cnt=0;//节点标记重置
    memset(tree,0,sizeof(tree)); //树重置
}
void insert(int x){
    int t;
    root=0;//必须起点为0 来表示树的开始
    for(int i=31;i>=0;i--){//从尾部向前
        t=(x>>i)&1;//获得每一位数字(0/1)
        if(tree[root][t]==0) tree[root][t]=++cnt;
        root=tree[root][t];
    }
}
int find(int y){
    int t,ans=0;
    root=0;
    for(int i=31;i>=0;i--){
        t=!((y>>i)&1);//异或最大  要求对应为 不同
        if(tree[root][t]) //求最大值 ans
         ans+=(t*(1<<i)),root=tree[root][t];
        else
        ans+=(!t*(1<<i)),root=tree[root][!t];
        //不存在 +不存在的对应的反值(一定存在);
        //根的指向 -->同理
    }
    return ans;
}
int main()
{
    int t;
    //所有输入输出必须用scanf();以及 printf();不然超时 -_-
    scanf("%d",&t);
    for(int j=1;j<=t;j++){
        init();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            insert(a[i]);
        }
        for(int i=0;i<m;i++)
            scanf("%d",&b[i]);
        printf("Case #%d:\n",j);
        for(int i=0;i<m;i++){
            int ans=find(b[i]);
            printf("%d\n",ans);
        }
    }
     return 0;
}

例题 HDU 2222 Keywords Search

问题分析:

AC自动机(多模式串匹配)的模板题 (感较很难哇...好久才理解)
ac自动机,其中 有字典树的内容,kmp的思想
字典树:建立树优化 查询
fail(失败指针):匹配失败是直接指向一个最长后缀
具体看代码内分析(很详细)
我学习的视频链接(代码来源)
B站大佬AC自动机

AC代码如下:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxx=1e6+10;// 建树节点个数
const int maxn=500005; //建树 大小
struct state{//每个节点参数
    int next[26];//下一节点
    int fail,cnt;// 失败指向节点存贮    --   节点区分标志
}p[maxn];//建树结构体大小

int size;//节点区分参数

void init(){//多组输入  初始化

for(int i=0;i<maxn;i++){
memset(p[i].next,0,sizeof(p[i].next));//初始化 指向
    p[i].fail=p[i].cnt=0;// 初始化失败指向  --   初始化节点标记
}
size=1;//  首节点 复赋值
}
queue<int> q;  //构建fail队列创建
void insert( char*s){
    int n=strlen(s);
    int now=0;
    for(int i=0;i<n;i++){
        char c=s[i];
        if(!p[now].next[c-'a'])//如果不在树中
         p[now].next[c-'a']=size++;//给与节点 变成树中一部分
        now=p[now].next[c-'a'];//子节点变成新的父节点
    }
    p[now].cnt++; //统计 单词 出现的次数
}
void build(){
    p[0].fail=-1; //0项失败没有指向
    q.push(0);//送入最初值
    while(q.size()){
        int u=q.front(); //队列首元素
        q.pop();
        for(int i=0;i<26;i++){ //扫描 队首元素的下一子节点
            if(p[u].next[i]){  //如果存在
                if(u==0)  //为祖先 (就是0)
                p[p[u].next[i]].fail=0;//指向祖先
                else
                {
                    int v=p[u].fail;//赋值 失败指向位置
                while(v!=-1){//不为祖先(就是0的指向)失败指向
                    if(p[v].next[i]){//存在
                        p[p[u].next[i]].fail=p[v].next[i];
                        //  (存在点<父类>的指向节点<子类>)
                        //的失败指向 (失败指向的节点<自雷>)
                        break;
                    }
                    v=p[v].fail;//指向自己的失败指向
                }
                if(v==-1)//为祖先
                p[p[u].next[i]].fail=0;
                }
            q.push(p[u].next[i]);//送入先的节点(子类)作为父类 构建fail
        }
    }
}
}
int get(int u){//防重复计算 (先看下面的match)
    int res=0;
    while(u){
        res+=p[u].cnt;//累加统计
        p[u].cnt=0;//结尾重置
        u=p[u].fail;//结尾直接指向fail优化查找
    }
    return res;
}
int match(char *s){//字符串查找
    int n=strlen(s);
    int res=0,now=0;
    for(int i=0;i<n;i++){
        char c=s[i];
        if(p[now].next[c-'a'])//存在指向父类
        now=p[now].next[c-'a'];
        else{//不存在使用fail跳转
            int pp=p[now].fail;//失败指向节点 赋值
            while(pp!=-1&&p[pp].next[c-'a']==0)
            //不为祖先(0)并且父类的子节点存在
                pp=p[pp].fail;//直至走到 祖先或者树分支的结尾
            if(pp==-1)//最终fail指向祖先
            now=0;//指向祖先
            else
            now=p[pp].next[c-'a'];//指向fail
        }
        if(p[now].cnt)//是都为树分支结尾(单词最后一个单词节点)
        res+=get(now);//次数累加到总计
    }
    return res;
}
    /*当时自己看的这段很懵逼 ****
    为啥没有一个一个和字符串
    比较  ...现在想想,笑哭 ```
    1.其时有比较操作请看 for()循环的第一个 if()呢就是
    比较操作
    2.而后来的else  是fail的跳转 作用就是用来优化比较操作
    这一点和  kmp非常相似
    */
char s[maxx];//创建单词数组
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%s",s);
            insert(s);//构建每一个单词到树中
        }
        scanf("%s",s);
        build();//树中各节点 用fail串联  的创建
        printf("%d\n",match(s));
    }
    return 0;
}