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

2019-11-14 11:31:35

字体：大中小

来源：转载

供稿：网友

C. Watto and Mechanismtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 3aaaaaacacacaaabaaccacacccaaacOutputYESNONO
题目大意：
给你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 3typedef 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");        }    }}