[poj] 1816 Wild words

原题

就是把find换成了dfs的Trie。
唯一要注意的就是当已经匹配完当前后，还要向下找所有的位置，因为可以为空！

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define N 100010
using namespace std;
int n,m,head[20*N],now,l,cnt=2,ans;
bool p[N];
char s[30];
struct hhh
{
    char to;
    int next,num;
    bool is;
    vector <int> v;
}edge[20*N];

void add(int u,char v)
{
    edge[cnt].is=0;
    edge[cnt].num=0;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void insert(int x)
{
    now=1;
    bool b;
    l=strlen(s+1);
    for (int i=1;i<=l;i++)
    {
	b=0;
	for (int j=head[now];j;j=edge[j].next)
	    if (edge[j].to==s[i]) b=1,now=j;
	if (!b) add(now,s[i]),now=head[now];
    }
    edge[now].v.push_back(x);
    edge[now].is=1;
}

void check(int now,int pos)
{
    if (pos==l+1)
    {
	if (edge[now].is)
	{
	    int pp=edge[now].v.size();
	    for (int i=0;i<pp;i++) ans++,p[edge[now].v[i]]=1;
	}
	for (int i=head[now];i;i=edge[i].next)
	    if (edge[i].to=='*') check(i,pos);
	return ;
    }
    for (int i=head[now];i;i=edge[i].next)
    {
	if (edge[i].to=='?' || edge[i].to==s[pos]) check(i,pos+1);
	if (edge[i].to=='*')
	{
	    for (int j=pos;j<=l+1;j++)
		check(i,j);
	}
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
	scanf("%s",s+1);
	insert(i);
    }
    for (int i=1;i<=m;i++)
    {
	scanf("%s",s+1);
	l=strlen(s+1);
	for (int j=0;j<=n;j++) p[j]=0;
	ans=0;
	check(1,1);
	if (!ans)
	{
	    printf("Not match
");
	    continue;
	}
	for (int j=0;j<=n;j++) if (p[j]) printf("%d ",j-1);
	printf("
");
    }
    return 0;
}