题目：[USACO14FEB]Auto-complete S

字典树套路题，字典树优化剪枝，加个cnt标记即可

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <iostream>

const int M=1e6+5;

using namespace std;

int tot,m,n,q;

char s[1005];

namespace trietree

{

	struct trie

	{

		int son[26],sum,tag;

	}e[M];

	void insert(int len,int id)

	{

		int p=0;

		for(int i=0;i<len;i++)

		{

			int k=s[i]-'a';

			if(!e[p].son[k])

			    e[p].son[k]=++tot;

			e[p].sum++;

			p=e[p].son[k];

		}

		e[p].sum++;

		e[p].tag=id;

	}

	int dfs(int p,int pos)

	{

		if(e[p].tag && pos==1)

		    return e[p].tag;

		if(e[p].tag)

		    pos--;

		if(!pos)

		    return e[p].tag;

		int ok=0;

		for(int i=0;i<26;i++)

		{

			if(!e[p].son[i])

			    continue;

			if(e[e[p].son[i]].sum>=pos)

			    return dfs(e[p].son[i],pos);

			pos-=e[e[p].son[i]].sum;

		}

		return -1;

	}

	int query(int len)

	{

		int p=0;

		for(int i=0;i<len;i++)

		{

			int k=s[i]-'a';

			if(!e[p].son[k])

			    return -1;

			p=e[p].son[k];

		}

		return dfs(p,m);

	}

}

using namespace trietree;

int main()

{

	ios::sync_with_stdio(0);

	cin>>n>>q;

	for(int i=1;i<=n;i++)

	{

		cin>>s;

		int len=strlen(s);

		insert(len,i);

	}

	while(q--)

	{

		cin>>m>>s;

		int len=strlen(s);

		cout<<query(len)<<'\n';

	}

	return 0;

}

巴特西

2022春每日一题：Day 37

题目：[USACO14FEB]Auto-complete S

最新文章

热门文章