HDU 6096 String

发表于 | 分类于 | ℃热度
~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

#.String

题面

Bob has a dictionary with $N$ words in it.

Now there is a list of words in which the middle part of the word has continuous letters disappeared. The middle part does not include the first and last character.

We only know the prefix and suffix of each word, and the number of characters missing is uncertain, it could be $0​$. But the prefix and suffix of each word can not overlap.

For each word in the list, Bob wants to determine which word is in the dictionary by prefix and suffix.

There are probably many answers. You just have to figure out how many words may be the answer.

简要翻译

给定$n$个串，有$m$次询问，每次询问给定串$a,b$，问$n$个串中有多少个能表示为$axb$，其中$x$为任意字符串。

Input

第一行给出一个整数$T$，代表数据的组数。

每一组数据包含$2​$个整数$n​$和$q​$， 分别代表串的个数和询问个数。

以下$n$行每行包含一个字符串$W_i$。

以下$q$行每行包含两个串$a_i$串$b_i$。

保证所有的串都是小写字母。

Output

对于每组数据，输出包含$q$行，每行包含一个整数代表答案。

Sample Input

1
4 4
aba
cde
acdefa
cdef
a a
cd ef
ac a
ce f

Sample Output

2
1
1
0

Hint

$T\le 5$

$0< n,q\le 100,000$

$\sum S_i+P_i\le 500,000​$

$\sum W_i\le 500,000$

条件等价于前缀为$a$，后缀为$b$，且长度$>=|a|+|b|$的个数。

在不考虑长度的情况下，将正串和反串分别按字典序编号，一个询问对应了编号的一个区间，用$Trie$树或排序+二分+$hash​$求出区间，然后用主席树来求答案。

然后考虑减掉长度不足的，直接枚举长度就可以确定字符串。

时间复杂度为$O(slogs)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,w=0;
	char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return w? -x:x;
}
const int N=2e6+5e5;
const int NS=5e5+10;
struct trie_tree
{
	int nxt[27],w;
}t[N];
struct block
{
	int l,r;
	friend bool operator < (block a,block b)
	{
		return a.r-a.l<b.r-b.l;
	}
}a[NS];
struct data
{
	int l,r,s;
	int ll,rr;
	friend bool operator < (data a,data b)
	{
		return a.r-a.l+a.rr-a.ll<b.r-b.l+b.rr-b.ll;
	}
}b[NS];
#define DS(x) x-'a'
int T,res,next_(1);
char s1[NS],s2[NS];
char s[NS],ss[NS];
int n,m,ans[NS];
int add()
{
	memset(&t[next_],0,sizeof(trie_tree));
	return next_++;
}
void insert(char *c)
{
	int rot=0,len=strlen(c);
	for(int i=0;i<len;++i)
	{
		int k=DS(c[i]);
		++t[rot].w;
		if(!t[rot].nxt[k]) t[rot].nxt[k]=add();
		rot=t[rot].nxt[k];
	}
	++t[rot].w;
}
void sub1(int x)
{
	int l=a[x].l,r=a[x].r;
	int sum=0;
	for(int i=l;i<r;++i)
	{
		s[sum++]=ss[i];
		s[sum++]=ss[r+l-i-1];
	}
	s[sum]=0;
}
int sub2(int x)
{
	int le1=b[x].r-b[x].l,le2=b[x].rr-b[x].ll;
	int maxn=max(le1,le2);
	int sum=0;
	for(int i=0;i<maxn;++i)
	{
		if(i<le1) s[sum++]=s1[i+b[x].l];
		else s[sum++]='$';
		if(le2-i-1>=0) s[sum++]=s2[b[x].rr-i-1];
		else s[sum++]='$';
	}
	s[sum]=0;
	res=0;
	return sum;
}
void calc(int x,int lenth,int root)
{
	if(x==lenth)
	{
		res+=t[root].w;
		return;
	}
	if(s[x]=='$')
	{
		for(int i=0;i<26;++i)
		{
			if(t[root].nxt[i])
				calc(x+1,lenth,t[root].nxt[i]);
		}
	}
	else
	{
		if(t[root].nxt[s[x]-'a'])
			calc(x+1,lenth,t[root].nxt[s[x]-'a']);
	}
}
int main()
{
	T=read();
	while(T--)
	{
		memset(&t[0],0,sizeof(trie_tree));
		next_=1;
		n=read(),m=read();
		int sum=0;
		for(int i=0;i<n;++i)
		{
			scanf("%s",ss+sum);
			a[i].l=sum;
			sum+=strlen(ss+sum);
			a[i].r=sum;
		}
		sort(a,a+n);
		int sum1=0,sum2=0;
		for(int i=0;i<m;++i)
		{
			scanf("%s %s",s1+sum1,s2+sum2);
			b[i].l=sum1,b[i].ll=sum2;
			sum1+=strlen(s1+sum1);
			sum2+=strlen(s2+sum2);
			b[i].r=sum1,b[i].rr=sum2;
			b[i].s=i;
		}
		sort(b,b+m);
		int p=n-1;
		for(int i=m-1;~i;--i)
		{
			while(a[p].r-a[p].l>=b[i].r-b[i].l+b[i].rr-b[i].ll&&p<n)
			{
				sub1(p--);
				insert(s);
			}
			sum=sub2(i);
			res=0;
			calc(0,sum,0);
			ans[b[i].s]=res;
		}
		for(int i=0;i<m;++i)
			printf("%d\n",ans[i]);
	}
	return 0;
}
-------------本文结束(づ￣ 3￣)づ~感谢您的阅读(*╹▽╹*)-------------