一.字符串

1.kmp

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48) ;
    if(f)x=-x;
}

const int maxn=1e6+6;
int n,m,p[maxn];
char s[maxn],ss[maxn];

inline void pre()
{
    int j=0;
    p[0]=-1;
    inc(i,0,m-1)
    {
        j=p[i];
        while(j!=-1&&ss[i]!=ss[j])j=p[j];
        p[i+1]=((~j)?(ss[i]==ss[j]?++j:0):0);
    }
}

inline void kmp()
{
    int j=0;
    inc(i,0,n-1)
    {
        while(j!=-1&&s[i]!=ss[j])j=p[j];
        ++j;
        if(j==m)
        {
            printf("%d\n",i+1-j+1);
            j=p[j];
        }
    }
}
int main()
{
    freopen("a.in","r",stdin);
    scanf("%s%s",s,ss);
    n=strlen(s);m=strlen(ss);
    pre();
    kmp();
    inc(i,1,m)
    printf("%d ",p[i]);
    re 0;
 }

View Code

2.trie

01trie

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48) ;
    if(f)x=-x;
}

const int maxn=1e5+5;
int n,m,hd[maxn];
struct node{
    int to,nt,val;
}e[maxn<<1];
int k;
inline void add(int x,int y,int z)
{
    e[++k]=(node){y,hd[x],z};hd[x]=k;
}

int dis[maxn];
inline void dfs(int x,int fa)
{
    for(int i=hd[x];i;i=e[i].nt)
    {
        int v=e[i].to;
        if(v==fa)continue;
        dis[v]=dis[x]^e[i].val;
        dfs(v,x);
    }
}

#define dec(i,l,r) for(int i=l;i>=r;--i)

int tr[maxn*30][2],tot,ans;
inline void insert(int x)
{
    int u=0;
    dec(i,30,0)
    {
        int now=(x>>i)&1;
        if(!tr[u][now])tr[u][now]=++tot;
        u=tr[u][now];
    }
}
inline void find(int x)
{
    int u=0;
    int cnt=0;
    dec(i,30,0)
    {
        int now=(x>>(i))&1;
        if(tr[u][now^1])
        {
            cnt+=1<<i;
            u=tr[u][now^1];
        }
        else u=tr[u][now];
    }
    ans=max(ans,cnt);
}

int main()
{
    freopen("a.in","r",stdin);
    rd(n);
    int x,y,z;
    inc(i,2,n)
    {
        rd(x),rd(y),rd(z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,0);
    inc(i,1,n)
    {
        find(dis[i]);
        insert(dis[i]);
    }
    printf("%d",ans);
    re 0;
}

View Code

trie的字符版就看看ac自动机就好了

3.ac自动机

ac自动机

模板

一.字符串