特判大法吼
by ghy21 @ 2018-09-15 16:52:26
@[ghy21](/space/show?uid=100036) 智熄的操作23333
by 萌田薰子 @ 2018-09-17 21:39:40
# 我也是这样
和你这个输出一毛一样
by xu_mengnan @ 2018-09-27 12:40:32
@[一之濑琴美](/space/show?uid=72408)
@[xu_mengnan](/space/show?uid=132936)
你可能没有考虑后缀从属关系（就是子串），弄个lst数组，记录上一个标记位置，在AC自动机构造时做出来，查询时每次都查询后缀就行了
代码
```cpp
inline void build(){
he = ta = 0;
for (register int i = 0; i < 26; i++)
if (ch[0][i] > 0) q[ta++] = ch[0][i];
while (he != ta){
register int u = q[he++]; if (he == Q) he = 0;
for (register int i = 0; i < 26; i++){
register int v = ch[u][i];
if (v == 0) ch[u][i] = ch[nt[u]][i];
else{
nt[v] = ch[nt[u]][i];
if (bo[nt[v]] > 0) lst[v] = nt[v];//这个位置记录后缀位置
else lst[v] = lst[nt[v]];
q[ta++] = ch[u][i]; if (ta == Q) ta = 0;
}
}
}
}
inline void query(register char *s){
register int len = strlen(s + 1), u = 0, mx = 0;
for (register int i = 1; i <= len; i++){
register int c = s[i] - 'a';
u = ch[u][c];
register int v = u;
while (v > 0){//在这里不断查询后缀
if (bo[v] != 0){
cnt[bo[v]]++;
if (bo[v] != 0) mx = max(mx, cnt[bo[v]]);
}
v = lst[v];
}
}
printf("%d\n", mx);
for (register int i = 1; i <= n; i++)
if (cnt[i] == mx) printf("%s\n", t[i] + 1);
}
```
by yy1695651 @ 2018-11-18 16:37:02
当然也可以沿着nt扫一遍，但慢了3000ms
by yy1695651 @ 2018-11-18 16:41:24
可以做下
单词https://www.luogu.org/recordnew/lists?uid=76226
P3966 [TJOI2013]单词
这道题
会有更深的理解
by yy1695651 @ 2018-11-18 16:43:00
https://www.luogu.org/problemnew/show/P3966
发错了
by yy1695651 @ 2018-11-18 16:43:46
@[yy1695651](/space/show?uid=76226) orz
by 萌田薰子 @ 2018-11-19 22:08:44
@[yy1695651](/space/show?uid=76226) 谢谢，解决了。
by xu_mengnan @ 2018-12-03 13:57:35