非指针字典树求调QwQ
查看原帖
非指针字典树求调QwQ
463210
zzzYheng楼主2021/7/10 15:22
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
struct node
{
	int id;
	int nxt[30];
}root,t[MAXN];
int n,m;
char ch[MAXN][55];
int cnt;
void build(char s[],int len,int id)
{
	int i,j;
	node &now=root;
	for(i=1;i<=len;i++)
	{
		int tmp=s[i]-'a'+1;
		if(now.nxt[tmp]==0)
			now.nxt[tmp]=++cnt;
		now=t[now.nxt[tmp]];
	}
	now.id=id;
}
int query(char s[],int len)
{
	int i,j;
	node &now=root;
	for(i=1;i<=len;i++)
	{
		int tmp=s[i]-'a'+1;
		if(now.nxt[tmp]==0)
			return -1;
		else now=t[now.nxt[tmp]];
		if(i==len&&now.id>0)
		{
			now.id=-1;
			return 1;
		}
		else if(i==len&&now.id==0)
			return -1;
		else if(i==len&&now.id==-1)
			return 0;
	}
}
int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%s",ch[i]+1);
		build(ch[i],strlen(ch[i]+1),i);
//		cout<<root.nxt[(int)(ch[i][1]-'a'+1)]<<endl;
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		char s[55];
		scanf("%s",s+1);
		int tmp=query(s,strlen(s+1));
		if(tmp==1) printf("OK\n");
		else if(tmp==-1) printf("WRONG\n");
		else printf("REPEAT\n");
	}
	return 0;
}
2021/7/10 15:22
加载中...