Codeforces 514C Watto and Mechanism【字典樹+Dfs】好題！

2019-11-14 10:09:12

字體：大中小

供稿：網(wǎng)友

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的內(nèi)存是肯定夠用的，這里大可不必擔(dān)心。
2、建好樹之后窩一開始只會暴力啊。暴力改變每個查詢串每個位子上的字符，然后查詢，顯然時間復(fù)雜度達到了O（M*（2len）^2）；那么考慮能否通過剪枝來優(yōu)化。
剪枝優(yōu)化是的確存在的，然而我們不能很簡單的找到剪枝點。
那么考慮Dfs。
對于不能繼續(xù)查詢的部分（p==NULL）進行剪枝。
細節(jié)處理有很多。大家注意一點就好。
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");        }    }}