Subtask1 除最后两个点外均 AC。
#7: Wrong Answer.
wrong answer On line 1 column 1,
read 2, expected 5.
#8: Wrong Answer.
wrong answer On line 1 column 1,
read 1, expected 4.
另外,Subtask2 已全部 TLE,咋个状压法求教,没太看懂。
代码:
#include <bits/stdc++.h>
using namespace std;
struct Node {
bool sucs;
int sub[26];
int fa, fail, dep;
}t[1024];
int n,m, cnt;
char wd[32][32], docm[2000024];
bool sf[2000024];
inline int len(char *str) {
int ret = 0;
while(str[ret]) ret++;
return ret;
}
inline int get_fail(int nid, int ch) {
nid = t[nid].fa;
while(nid && !~t[t[nid].fail].sub[ch]) {
nid = t[nid].fa;
}
return nid == 0 ? 0 : t[t[nid].fail].sub[ch];
}
int main() {
scanf("%d %d", &n, &m);
t[0].sucs = false;
for(int i = 0; i<26;i++) t[0].sub[i]=-1;
t[0].fail = 0;
t[0].fa = 0;
t[0].dep = 0;
int wnodes[32],depths[32];
int max_depth = 0;
for(int i=0; i<n;i++) {
scanf("%s", wd[i]);
depths[i] = len(wd[i]);
wnodes[i] = 0;
if(depths[i] > max_depth) max_depth = depths[i];
}
int d;
for(int i = 0; i<max_depth; i++) {
for(int j=0; j<n;j ++) if(i < depths[j]) {
d = wnodes[j];
if(!~t[d].sub[wd[j][i]-'a']) {
t[d].sub[wd[j][i]-'a']=++cnt;
t[cnt].sucs = false;
for(int k = 0;k<26;k++) {
t[cnt].sub[k] = -1;
}
t[cnt].fa = d;
t[cnt].fail = get_fail(cnt, wd[j][i]-'a');
t[cnt].dep = t[d].dep + 1;
}
d = t[d].sub[wd[j][i]-'a'];
wnodes[j] = d;
}
}
for(int i=0;i<n;i++) t[wnodes[i]].sucs=true;
for(int i=0;i<m;i++) {
scanf("%s", docm);
int d = 0, wl = len(docm), ans = 0, xd;
for(int j = 0; j < wl; j++) {
while(!~t[d].sub[docm[j]-'a'] && d) {
d = t[d].fail;
}
if(~t[d].sub[docm[j]-'a']) {
d = t[d].sub[docm[j] - 'a'];
}
xd = d;
sf[j] = false;
while(~xd) {
if(t[xd].sucs) {
if(t[xd].dep == j + 1) {
sf[j] = true;
ans = j+1;
} else if(sf[j - t[xd].dep]) {
sf[j] = true;
ans = j+1;
}
}
if(xd == 0) break;
xd = t[xd].fail;
}
}
printf("%d\n",ans);
}
return 0;
}