提高A组模拟词典

wjh15101051's space

卧薪尝胆，厚积薄发。

提高A组模拟词典

Date: Sun Aug 12 16:03:37 CST 2018

In Category: NoCategory

Description：

$n$ 个字符串，每次询问一个字符串不是区间内任何一个字符串的前缀的区间最长是多少。

$1\le n \le 10^5$ $1\le m \le 10^5$

Solution：

把所有模板串建 $trie$ 树，每个节点维护两个值：这个节点表示的字符串不是区间内任何一个字符串的前缀的最长区间长度 $maxl$ 和上一次经过这个点是哪个字符串 $last$ ，插入时每经过这个点就用 $now-last-1$ 更新 $ans$ ，并把 $last$ 设成 $now$ ，查询时只要找到对应节点即可直接返回答案，注意如果没有对应节点返回 $n$ ，在最后应特殊处理结尾是一个区间的情况。

Code:


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define MAXL 5000010

char c[MAXL];

struct node

{

	int c[3];

	int last,maxl;

	node(){last = maxl = 0;}

}t[MAXL];

int root;

int ptr = 0;

int newnode(){return ++ptr;}

void insert(char ch[],int now)

{

	int l = strlen(ch + 1);

	int cur = root;

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

	{

		if(t[cur].c[ch[i] - 'a'] == 0)t[cur].c[ch[i] - 'a'] = newnode();

		cur = t[cur].c[ch[i] - 'a'];

		t[cur].maxl = max(t[cur].maxl,now - t[cur].last - 1);

		t[cur].last = now;

	}

	return;

}

int query(char ch[])

{

	int cur = root;

	int l = strlen(ch + 1);

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

	{

		if(t[cur].c[ch[i] - 'a'] == 0)return n;

		cur = t[cur].c[ch[i] - 'a'];

	}

	return t[cur].maxl;

}

int main()

{

	freopen("word.in","r",stdin);

	freopen("word.out","w",stdout);

	scanf("%d%d",&n,&m);

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

	{

		scanf("%s",c + 1);

		insert(c,i);

	}

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

	{

		t[i].maxl = max(t[i].maxl,n - t[i].last);

	}

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

	{

		scanf("%s",c + 1);

		printf("%d\n",query(c));

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}

In tag: 数据结构-trie树

wjh15101051