P2292,第二个点洛谷显示WA,本地显示RE
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
#define R register
#define U unsigned
#define qwq printf("qwq\n")
const int N = 205, M = 2e6 + 5;
int n, m, tot = 1, len, ans;
int trie[N][30];
char s[M];
bool End[N];
inline int max (int a, int b) {return (a)>(b)?(a):(b);}
void insert (char a[]) {
int len = strlen(a), p = 1;
for (int i = 0; i < len; ++i) {
//printf("%c\n", a[i]);
int ch = a[i] - 'a';
if (!trie[p][ch]) trie[p][ch] = ++tot;
p = trie[p][ch];
}
//printf("\n");
End[p] = 1;
}
void find (int pos, int p, int cnt) {
printf("%d %d %d\n", pos, p, cnt);
for (int i = pos; i < len; ++i) {
if (pos == 88314 && p == 1 && cnt == 88314) qwq;
if (pos == 88314 && p == 1 && cnt == 88314) printf("%d\n", trie[p][s[i] - 'a']);
if (pos == 88314 && p == 1 && cnt == 88314) qwq;
if (pos == 88314 && p == 1 && cnt == 88314) printf("%d\n", s[i] - 'a');
p = trie[p][s[i] - 'a'];
if (pos == 88314 && p == 1 && cnt == 88314) printf("%d\n", p);
if (pos == 88314 && p == 1 && cnt == 88314) qwq;
if (!p) return;
if (pos == 88314 && p == 1 && cnt == 88314) qwq;
++cnt;
if (End[p]) {
ans = max(ans, cnt);
find(i + 1, 1, cnt);
find(i + 1, p, cnt);
return;
}
}
ans = max(ans, cnt);
}
int main () {
freopen("2.in", "r", stdin);
//freopen("data.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
char a[12];
scanf("%s", a);
insert(a);
}
for (int i = 1; i <= m; ++i) {
scanf("%s", s);
ans = 0;
len = strlen(s);
find(0, 1, 0);
printf("%d\n", ans);
}
return 0;
}/*what is you your name
whatisyourname
使用单词what is your name时,可以理解上面句子
但是使用单词what is you name时无法理解
也就是说,如果trie当前节点有End标记且未结束时
要考虑回头或继续往下走*/
第二个测试点(提取码:1pwd)(第二个点太大了,剪贴板装不下)
运行结果:)
find函数里的前4个if都运行了,说明数组不可能越界,但是第5个if就没有运行了...求问哪儿出问题了qwq