两份不同的代码,提交却都 AC 了。
理应 AC 代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m;
int son[N][26], idx;
bool v[N * 60];
map<string, bool> vis;
void I(string s){
int p = 0;
for(int i = 0; i < s.size(); i++){
int u = s[i] - 'a';
if(!son[p][u]){
son[p][u] = ++idx;
}
p = son[p][u];
}
v[p] = true;
}
bool Q(string s){
int p = 0;
for(int i = 0; i < s.size(); i++){
int u = s[i] - 'a';
if(!son[p][u]){
return false;
}
p = son[p][u];
}
return v[p];
}
void Solve(){
cin >> n;
string s;
for(int i = 1; i <= n; i++){
cin >> s;
I(s);
}
cin >> m;
for(int i = 1; i <= m; i++){
cin >> s;
bool f = Q(s);
if(!vis[s] && f){
cout << "OK\n";
vis[s] = true;
}
else if(f){
cout << "REPEAT\n";
}
else if(!f){
cout << "WRONG\n";
}
}
}
int main(){
Solve();
return 0;
}
理应 WA 却 AC 的代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m;
int son[N][26], idx;
map<string, bool> vis;
void I(string s){
int p = 0;
for(int i = 0; i < s.size(); i++){
int u = s[i] - 'a';
if(!son[p][u]){
son[p][u] = ++idx;
}
p = son[p][u];
}
}
bool Q(string s){
int p = 0;
for(int i = 0; i < s.size(); i++){
int u = s[i] - 'a';
if(!son[p][u]){
return false;
}
p = son[p][u];
}
return true;
}
void Solve(){
cin >> n;
string s;
for(int i = 1; i <= n; i++){
cin >> s;
I(s);
}
cin >> m;
for(int i = 1; i <= m; i++){
cin >> s;
bool f = Q(s);
if(!vis[s] && f){
cout << "OK\n";
vis[s] = true;
}
else if(f){
cout << "REPEAT\n";
}
else if(!f){
cout << "WRONG\n";
}
}
}
int main(){
Solve();
return 0;
}
可以看出,当询问的一个字符串是其中一个字符串的前缀而并没有实质性出现时,第二份代码会出错,而第一份不会。
可以被以下数据卡掉:
5
addddfdf
trttyty
fdgtfhfg
wsghtdffg
rdsgtrsgdg
5
add
trt
fdg
wsght
rdsg
第一份代码输出:
WRONG
WRONG
WRONG
WRONG
WRONG
而第二份代码输出:
OK
OK
OK
OK
OK
希望加强数据。