技术教程 编程教程 KMP,HASH,Trie,AC自动机 正文

KMP,HASH,Trie,AC自动机

2023-03-18,,

　　我做个总结算了下午看了一下AC自动机和学习我的大生物（当然是多谢鑫神了）。。完了要崩。。

1 KMP 只要是学过的人都觉得比较简单吧 但是学不会的人就感觉很难了，我是那种顿悟的然后感觉非常简单的人过程需要自己来体会言传不如身教用身心去体会这个过程就可以成功了。

一种快速匹配子串的东西。具体来说 证明我就不在证了先对自我进行匹配求出nex数组然后和文本串进行匹配考虑这样当我们匹配刚好失配的时候此时还有价值的匹配只能是前面的前缀和当前的东西匹配上了这样才会有价值的匹配不然前面的串往后移动一个距离还是会失配，因为到达改点的时候还是会失配。这样我们每次都利用有价值的匹配实现时间复杂度为O(n);

#include<bits/stdc++.h>

#include<iostream>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<iomanip>

#include<algorithm>

#include<queue>

#include<vector>

#include<stack>

#include<cstdio>

#include<map>

#include<deque>

#include<set>

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

char a[maxn],b[maxn];

int nex[maxn],len,tot;

void KMP()

{

    int j=;

    nex[]=;

    for(int i=;i<=tot;i++)

    {

        while(j&&b[j+]!=b[i])j=nex[j];

        if(b[j+]==b[i])j++;

        nex[i]=j;

    }

    j=;

    for(int i=;i<=len;i++)

    {

        while(j&&b[j+]!=a[i])j=nex[j];

        if(a[i]==b[j+])j++;

        if(j==tot)

        {

            printf("%d\n",i-j+);

            j=nex[j];

        }

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    scanf("%s",a+);scanf("%s",b+);

    len=strlen(a+);tot=strlen(b+);

    KMP();

    for(int i=;i<=tot;i++)printf("%d ",nex[i]);

    return ;

}

具体就是这样了真的不清楚的话就自己晚上睡觉前思考一下，体会一下这美妙的过程。。

当然我才知道有扩展KMP开个坑，以后填！

扩展KMP：

2 HASH hash可能是初学者最容易理解的算法了我觉得，因为在一定的程度上它表现出来的是暴力的美学也是干净利索的做法。和字符串联系在一起自然是要进行字符串的hash。字符串的hash 的话我们采用字符赋值或者直接使用ASCll 也行但是这显然很容易就冲突了abc bca 直接GG 这里我们日常的hash是直接采用进制hash来搞一些操作。我们试想 a*p^3+b*p^2+c*p 这样和b*p^3+c*p^2+a*p 这样冲突的几率会非常的小或者说在一定的意义下是不可能冲突的因为这就不是一个hash了变成了一个p进制的数字对于这样的数字每个字符串都只能对应一个数字又何谈来冲突呢？数字太大存不下啊map！这个我还不如直接mapstring呢！也对哦那只能取模了模数大一点减少冲突几率然后操作是祷告自己欧皇附身取得模数没有冲突！挂链法好像不太好用嘞。。那我也没办法了。我们有h[i]数组表示前i个字符的hash值然后我们可以求出来任何一段的hash值只要不冲突我们这个就可以实现O(1)判断两个字符串是否相同了！！！这样的话写字符串的匹配应该也是O(1)的。本来是要表演一下hash 的但是无奈map还是比较好用的我没办法只能使用了hash。抱歉会就行了。

方一道比较有意思的hash题可惜了我并没有成就感因为这道题本质上并不是我思考出来的哎。

这道题比较有意思求一个字符串中出现的东西 搞一波事情吧对于最长的我们把整个m便利完了之后一定能够求出，此时对于某个点我们应该二分一个长度使其达到答案这个答案相当的不好判断啊。

但是转换一个问题 对于一个i这个单词我们主席树中开这个东西然后查询就行了 啊二分+可持久化一下即可。妙！一个字符串的题目被转换成了数据结构的题目我也是佩服。

考虑一种更优的方法是尺取法 对于 l r r向右移动当移动到某个点的时候此时单词都有了 l向右移动此时不断的更新答案然后r再向右我们O(n)的时间貌似是求出了这个东西采用hash的话我想是可以O(n)的操作难度较高我们采用一定不会冲突的map 此时我们直接开个数组表示某个字符串出现了几次即可。完事了。

//#include<bits/stdc++.h>

#include<iostream>

#include<queue>

#include<iomanip>

#include<cctype>

#include<cstdio>

#include<deque>

#include<utility>

#include<cmath>

#include<ctime>

#include<cstring>

#include<string>

#include<cstdlib>

#include<vector>

#include<algorithm>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define INF 1000000000

#define ll long long

#define R register

#define mod 1000000007

using namespace std;

inline void put(R int x)

{

    x<?putchar('-'),x=-x:;

    R int num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const int MAXN=;

int n,m,num,ans,s,answer=MAXN;

int vis[MAXN],cnt[MAXN];

map<string,int>k;

string a,b[MAXN];

int main()

{

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=;i<=n;++i)

    {

        cin>>a;

        if(!k[a])k[a]=++s;

        //cout<<a<<endl;

    }

    cin>>m;

    for(int i=;i<=m;++i)

    {

        cin>>b[i];

        vis[k[b[i]]]=;

        //cout<<b[i]<<endl;

    }

    for(int i=;i<=s;++i)if(vis[i])++ans;

    if(ans==){put(ans),put();return ;}

    for(int i=,j=;j<=m;++j)

    {

        int g=k[b[j]];

        if(g)

        {

            ++cnt[g];

            if(cnt[g]==)++num;

        }

        while(num==ans)

        {

            //cout<<j<<' '<<i<<endl;

            answer=min(answer,j-i);

            ++i;g=k[b[i]];

            if(g)

            {

                --cnt[g];

                if(cnt[g]==)--num;

            }

        }

    }

    put(ans);

    put(answer);

    return ;

}

这种尺取法显然是正确的如果非要证明的话我会采用一种答案最优性原则证明答案一定是答案所以这是正确的。

Trie 字典树啦很简单的东西可持久化的东西我想想好像是一个有根的东西等会我复习一下嘞。

首先是字典树我们对于根出发建立每一个单词的路径然后查询的时候直接查询即可。时间。

注意这里时间是总插入Trie数的字符串的长度而空间则是MAX最长子串*根的数量*子串数量*子串的最大数集。

很朴素的一道题目询问每篇文章出现了多少个单词其实就是建一颗Trie树在上面跑即可 然后我们考虑建文章的Trie树那么复杂度就是mn*20当然可以过但是我想AC自动机的话这个复杂度应该是O(m*5000)左右吧要快一点当然计算一下空间吧建文章的Trie 空间：n*5000*26=130000000*4=520000000b=520000kb=520MB刚好爆炸。。空间就给了128肿么办我的办法是直接开char 存。然后可以存下。

//#include<bits/stdc++.h>

#include<iostream>

#include<queue>

#include<iomanip>

#include<cctype>

#include<cstdio>

#include<deque>

#include<utility>

#include<cmath>

#include<ctime>

#include<cstring>

#include<string>

#include<cstdlib>

#include<vector>

#include<algorithm>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define INF 1000000000

#define ll long long

#define R register

#define l(x) c[x][0]

#define r(x) c[x][1]

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    R int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void put(R int x)

{

    x<?putchar('-'),x=-x:;

    R int num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const int MAXN=,maxn=;

int n,m,cnt,flag=;

int trie[MAXN][],p;

int c[];

bool vis[MAXN];

char a[][MAXN][];

char b[maxn][];

bitset<>used[maxn];

inline void insert(int i,int j)

{

    int len=strlen(a[i][j]);p=;

    for(int k=;k<len;++k)

    {

        int now=a[i][j][k]-'a';

        if(!trie[p][now])trie[p][now]=++cnt;

        p=trie[p][now];

    }

    vis[p]=;

}

inline void calculate(int j)

{

    int len=strlen(b[j]);p=;

    for(int k=;k<len;++k)

    {

        if(b[j][k]<'a'||b[j][k]>'z')continue;

        int now=b[j][k]-'a';

        if(!trie[p][now])return;

        p=trie[p][now];

    }

    if(vis[p])flag=;

}

int main()

{

    n=read();

    for(int i=;i<=n;++i)

    {

        c[i]=read();

        for(int j=;j<=c[i];++j)scanf("%s",a[i][j]);

    }

    m=read();

    for(int i=;i<=m;++i)scanf("%s",b[i]);

    for(int i=;i<=n;++i)

    {

        memset(trie,,sizeof(trie));

        memset(vis,,sizeof(vis));

        cnt=;

        for(int j=;j<=c[i];++j)insert(i,j);

        for(int j=;j<=m;++j)

        {

            flag=;

            calculate(j);

            if(flag)used[j][i]=;

        }

    }

    for(int j=;j<=m;++j)

    {

        flag=;

        for(int i=;i<=n;++i)

        if(used[j][i])

        {

            if(flag==){flag=;printf("%d",i);}

            else printf(" %d",i);

        }

        putchar('\n');

    }

    return ;

}

一直wa 的原因是vis数组竟然没开 不是开了我又删了。。

一道简单的Trie树+dp 暴力dp 出奇迹A了。

//#include<bits/stdc++.h>

#include<iostream>

#include<queue>

#include<iomanip>

#include<cctype>

#include<cstdio>

#include<deque>

#include<utility>

#include<cmath>

#include<ctime>

#include<cstring>

#include<string>

#include<cstdlib>

#include<vector>

#include<algorithm>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define INF 1000000000

#define ll long long

#define R register

#define l(x) c[x][0]

#define r(x) c[x][1]

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    R int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void put(R int x)

{

    x<?putchar('-'),x=-x:;

    R int num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const int MAXN=;

int n,p,cnt,m,maxx;

char b[],a[MAXN];

int trie[][];

int vis[];

int f[MAXN];

inline void insert()

{

    int len=strlen(b+);p=;

    for(int i=;i<=len;++i)

    {

        int now=b[i]-'a';

        if(!trie[p][now])trie[p][now]=++cnt;

        p=trie[p][now];

    }

    vis[p]=;

}

inline int query(int l,int r)

{

    p=;

    for(int i=l;i<=r;++i)

    {

        int now=a[i]-'a';

        if(!trie[p][now])return ;

        p=trie[p][now];

    }

    if(vis[p])return ;

    return ;

}

int main()

{

    n=read();m=read();

    for(int i=;i<=n;++i)scanf("%s",b+),insert();

    for(int i=;i<=m;++i)

    {

        scanf("%s",a+);

        memset(f,,sizeof(f));

        maxx=;f[]=;

        int len=strlen(a+);

        for(int j=;j<=len;++j)

        {

            int flag=;

            for(int k=j-<?:j-;k<j;++k)

            {

                if(!f[k])continue;

                flag=;

                f[j]|=f[k]&query(k+,j);

                if(f[j])break;

                //cout<<k<<' '<<f[k]<<endl;

                //cout<<query(k+1,j)<<endl;

            }

            if(f[j])maxx=max(maxx,j);

            if(!flag)break;

        }

        put(maxx);

    }

    return ;

}

AC自动机 为什么要叫自动很简单因为它可以自动的匹配模式串我们继续我们的话题上午有点跑偏了。。。

自动之意取自会自己进行匹配而不需要人工的让其专门的操作原因在于一个fail数组 自闭了 我不写了。

KMP,HASH,Trie,AC自动机的相关教程结束。

《KMP,HASH,Trie,AC自动机.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!