CodeForces - 514C Watto and Mechanism

题意：

先给n个字符串(由a，b,c组成)，再给m个查询，问存不存在和n个中的某一个只差一个字符
(0 ≤ n ≤ 3·10, 0 ≤ m ≤ 3·10)

题解：

n和m都很大
有两种做法：hash和字典树
就是很暴力的做法
把模板串整体哈希并记录值

然后依次改变目标串的每一位，改成a~c，然后查看是否存储过，没有就移动到下一位进行相同的操作

字典树
利用字典树处理前n个字符串，然后再字典树上跑dfs

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=6e5+9;
ll p[maxn];
set<ll>myset;
ll mod=1e12+7;
int main()
{
    p[0]=1;
    for(int i=1;i<=maxn;i++)
    {
        p[i]=(p[i-1]*131)%mod;
    }
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        ll sum=0;
        int len=s.length();
        for(int j=0;j<=len-1;j++)
        {
            sum=(sum*131+s[j]-'0')%mod;
        }
        myset.insert(sum);
    }
    for(int i=1;i<=m;i++)
    {
        string s;
        cin>>s;
        ll sum=0;
        ll ans=0;
        bool f=0;
        int len=s.length();
        for(int j=0;j<=len-1;j++)
        {
            sum=(sum*131+s[j]-'0')%mod;
        }
        for(int j=0;j<=len-1;j++)
        {
            if(f==1)break;    
            for(char x='a';x<='c';x++)
            {
                if(s[j]==x)continue;
                ans=(sum-(s[j]-'0')*p[len-j-1])%mod;
                if(ans<0)ans=(ans+mod)%mod;
                ans=(ans+(x-'0')*p[len-j-1])%mod;
                if(myset.count(ans))
                {
                    f=1;
                    break;
                }
            }


        }
        if(f)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }
    return 0;
}

字典树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <string>
#include <map>
#include <set>
#define LL long long
using namespace std;
#define maxn 300007
#define maxx 600007
#define maxNode 3
int num[maxn][3];
char s[maxx];
struct node
{
    node* next[maxNode];
    int flag;
};

node* createNode()
{
    node *q=new node;
    for(int i=0;i<maxNode;i++)
    {
        q->next[i]=NULL;
    }
    return q;
}
void insertNode(node *trie,char *c)
{
    int i=0;
    int k;
    node *p=trie;
    while(c[i])
    {
        k=c[i++]-'a';
        if(p->next[k]==NULL)
        {
            node *q=createNode();
            p->next[k]=q;
        }
        p=p->next[k];
    }
    p->flag=1;
}

int dfs(node *trie,char *c,int x)
{
    node *p=trie;
    int i,j;
    if(trie==NULL) return 0;
    if(c[0]=='\0')
    {
        if(x==1&&p->flag)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    for(i=0;i<3;i++)
    {
        if(c[0]=='a'+i)
        {
            if(dfs(trie->next[i],c+1,x)) return 1;
        }
        else if(x==0)
        {
            if(dfs(trie->next[i],c+1,1)) return 1;
        }
    }
    return 0;
}
int main()
{
    int len,n,i,j,k,m,x,y;
    scanf("%d%d",&n,&m);
    node *trie=createNode();
    for(i=1;i<=n;i++)
    {
        scanf("%s",s);
        insertNode(trie,s);
    }
    for(j=1;j<=m;j++)
    {
        scanf("%s",s);
        bool flag=0;
        for(i=0;i<3;i++)
        {
            if(s[0]=='a'+i)
            {
                if(dfs(trie->next[i],s+1,0))
                {
                    flag=1;
                    break;
                }
            }
            else if(dfs(trie->next[i],s+1,1))
            {
                flag=1;
                break;
            }
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}