hihocoder 1261 String Problem II (Trie树)

描述

我们有一个字符串集合S，其中有N个两两不同的字符串。还有M个询问，每个询问都会先给出一个字符串w，你需要回答以下三个问题：

1. 输出所有S的串中，可以由w恰好添加两个字符得到的串中，编号最小的3个。

2. 输出所有S的串中，可以由w修改不超过2个字符得到的串中，编号最小的3个。

3. 输出所有S的串中，可以由w删除恰好两个字符得到的串中，编号最小的3个。

字母可以添加在包括开头结尾在内的任意位置，比如在"abc"中添加"x"和"y"，可能可以得到"yxabc"，"aybxc"，"axbyc"等等的串。

所有字符串只由小写字母构成。

输入

第一行两个数N和M，表示集合S中字符串的数量和询问的数量。

接下来N行，其中第i行给出S中第i个字符串。第i个字符串的编号就是i。

接下来M行，其中第i行给出第i个询问串。

数据范围：

N,M<=10000。

S中字符串长度和<=100000。

所有询问中字符串长度和<=100000。

输出

对每个询问输出三行，每行三个数，分别表示每个问题编号最小的3个串的编号，从小到大排列。

如果不到3个串，则在最后用-1补到3个输出，比如如果结果是1和2，那么输出1 2 -1，如果S中没有满足条件的串，就输出-1 -1 -1。

样例输入

5 5
dsxmlkxp
asxglqkdxp
asxgavxp
asxglp
sxglkx
kebvpyky
hjpntqft
asxglkxp
polbmzgq
jdczlmtd

样例输出

-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
2 -1 -1
1 3 -1
4 5 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1

题目链接：http://hihocoder.com/problemset/problem/1261

题目分析：是1260的拓展，正解应该是字符串hash，Trie的复杂度理论会T，数据水了，Trie的思想和1260类似，就是在删除和修改的地方转移不同罢了，注意有个剪枝就是修改的时候如果枚举值和当前一样则跳过

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
int const MAX = 1e5 + 5;
int n, m, len;
char s[MAX];struct Trie
{int next[MAX * 26][26], id[MAX * 26], tot, root, num, cou, res[5];set <int> ans; set <int> :: iterator it;inline int Newnode(){memset(next[tot], -1, sizeof(next[tot]));return tot ++;}inline void Init(){tot = 0;root = Newnode();}inline void Clr(){cou = 0;ans.clear();}inline void Insert(char *s, int no){int p = root;for(int i = 0; i < (int) strlen(s); i++){int idx = s[i] - 'a';if(next[p][idx] == -1)next[p][idx] = Newnode();p = next[p][idx];}id[p] = no;}inline void DFS1(char *s, int pos, int p, int cnt){if(id[p] && cnt == 0 && pos == len){ans.insert(id[p]);return;}if(cnt > 0)for(int i = 0; i < 26; i++)if(next[p][i] != -1)DFS1(s, pos, next[p][i], cnt - 1);if(pos == len)return;int idx = s[pos] - 'a';if(next[p][idx] != -1)DFS1(s, pos + 1, next[p][idx], cnt);}inline void DFS2(char *s, int pos, int p, int cnt){if(id[p] && pos == len){ans.insert(id[p]);return;}int idx = s[pos] - 'a';if(cnt > 0 && pos <= len)for(int i = 0; i < 26; i++)if(next[p][i] != -1 && i != idx)DFS2(s, pos + 1, next[p][i], cnt - 1);if(pos == len)return;if(next[p][idx] != -1)DFS2(s, pos + 1, next[p][idx], cnt);}inline void DFS3(char *s, int pos, int p, int cnt){if(id[p] && pos == len && cnt == 0){ans.insert(id[p]);return;}if(cnt > 0)DFS3(s, pos + 1, p, cnt - 1);if(pos == len)return;int idx = s[pos] - 'a';if(next[p][idx] != -1)DFS3(s, pos + 1, next[p][idx], cnt);}inline void Output(){for(it = ans.begin(); it != ans.end() && cou != 3; it++)res[cou ++] = *it;for(int i = cou; i < 3; i++)res[i] = -1;printf("%d %d %d\n", res[0], res[1], res[2]);}}t;int main()
{t.Init();scanf("%d %d", &n, &m);for(int i = 0; i < n; i++){scanf("%s", s);t.Insert(s, i + 1);}for(int i = 0; i < m; i++){scanf("%s", s);len = strlen(s);t.Clr();t.DFS1(s, 0, t.root, 2);t.Output();t.Clr();t.DFS2(s, 0, t.root, 2);t.Output();t.Clr();t.DFS3(s, 0, t.root, 2);t.Output();}
}