Codeforces 514C Watto and Mechanism【字典树+Dfs】好题！

Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled withn strings. Then the mechanism should be able to process queries of the following type: "Given strings, determine if the memory of the mechanism contains stringt that consists of the same number of characters ass and differs from s in exactly one position".

Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting ofn initial lines and m queries. He decided to entrust this job to you.

Input

The first line contains two non-negative numbers n andm (0 ≤ n ≤ 3·10⁵,0 ≤ m ≤ 3·10⁵) — the number of the initial strings and the number of queries, respectively.

Next follow n non-empty strings that are uploaded to the memory of the mechanism.

Next follow m non-empty strings that are the queries to the mechanism.

The total length of lines in the input doesn't exceed 6·10⁵. Each line consistsonly of letters 'a', 'b', 'c'.

Output

For each query print on a single line "YES" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "NO" (without the quotes).

ExamplesInput

2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

Output

YES
NO
NO

题目大意：

给你N个原串，以及M个查询串。

每个查询串询问的是，原串中是否有一个字符串，通过改变一个字母就能得到这个字符串（要求其他位子的字符都要相等）。

思路：

1、首先字典树建树，因为只有3种字母，而且输入的总长度也并不大，所以256M的内存是肯定够用的，这里大可不必担心。

2、建好树之后窝一开始只会暴力啊。暴力改变每个查询串每个位子上的字符，然后查询，显然时间复杂度达到了O（M*（2len）^2）；那么考虑能否通过剪枝来优化。

剪枝优化是的确存在的，然而我们不能很简单的找到剪枝点。

那么考虑Dfs。

对于不能继续查询的部分（p==NULL）进行剪枝。

细节处理有很多。大家注意一点就好。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define maxn 3
typedef struct tree
{
    tree *nex[maxn];
    int v;
    int val;
}tree;
tree root;
void init()
{
    for(int i=0;i<maxn;i++)
    {
        root.nex[i]=NULL;
    }
}
void creat(char *str,int va)
{
    int len=strlen(str);
    tree *p=&root,*q;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'a';
        if(p->nex[id]==NULL)
        {
            q=(tree *)malloc(sizeof(root));
            for(int j=0;j<3;j++)
            {
                q->nex[j]=NULL;
            }
            p->nex[id]=q;
        }
        p=p->nex[id];
        if(i==len-1)
        {
            p->val=va;
        }
    }
}
char a[600600];
int find(int i,int flag,tree *p,int lenn)
{
    if(p==NULL)return 0;
    int id=a[i]-'a';
    tree *pre=p;
    p=pre->nex[id];
    if(i==lenn-1)
    {
        if(p!=NULL&&flag==1&&p->val==1)
        return 1;
        else if(flag==0)
        {
            p=pre->nex[(id+1)%3];
            if(p!=NULL&&p->val==1)return 1;
            p=pre->nex[(id+2)%3];
            if(p!=NULL&&p->val==1)return 1;
        }
        return 0;
    }
    int tmp=0;
    if(p!=NULL)if(find(i+1,flag,p,lenn)==1)tmp=1;
    if(flag==0)
    {
        p=pre->nex[(id+1)%3];
        if(p!=NULL)if(find(i+1,1,p,lenn)==1)tmp=1;
        p=pre->nex[(id+2)%3];
        if(p!=NULL)if(find(i+1,1,p,lenn)==1)tmp=1;
    }
    return tmp;
}
int n,m;
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=0;i<n;i++)
        {
            scanf("%s",a);
            creat(a,1);
        }
        while(m--)
        {
            int flag=0;
            scanf("%s",a);
            tree *p=&root;
            if(find(0,0,p,strlen(a))==1)printf("YES\n");
            else printf("NO\n");
        }
    }
}

秒客网

Codeforces 514C Watto and Mechanism【字典树+Dfs】好题！

相关文章