我把我自己思路实现的一份不知道是否正确的代码在本地过完样例之后交上去,结果 WA 穿了,由于本人刚刚学 OI,面对满屏大红大紫不知道哪里错了,下了一组数据:
// P3065_1.in
4
omm
moo
mom
ommnom
// P3065_1.out
2
omm
mom
我一看,这不就是样例吗?那我咋挖穿了啊?
于是,特来向各位爷求助。下附代码:
# include <bits/stdc++.h>
using namespace std;
namespace Elaina {
# define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
# define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
# define fi first
# define se second
# define mp(a, b) make_pair(a, b)
# define Endl putchar('\n')
# define mmset(a, b) memset(a, b, sizeof (a))
# define mmcpy(a, b) memcpy(a, b, sizeof (a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <class T> inline T fab(T x) { return x<0? -x: x; }
template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); }
template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); }
template <class T> inline T readin(T x) {
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template <class T> inline void writc(T x, char s='\n') {
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
} using namespace Elaina;
const int maxn=3e4;
const int maxlen=3e5;
const int sigma=26;
int n;
string s[maxn+5];
namespace saya {
int trie[maxlen+5][sigma];
int siz[maxlen+5], ncnt=1; // 1 is the root
bool flg[maxlen+5];
inline void insert(const char s[]) {
int len=strlen(s), now=1, to;
++siz[1]; // udpate the @p size[]
for(int i=0; i<len; ++i) {
to=s[i]-'a';
if(!trie[now][to]) trie[now][to]=++ncnt;
now=trie[now][to], ++siz[now];
} flg[now]=1; // put the ending tag
}
bool used[sigma]; int stk[sigma+1], ed;
inline bool query(const char s[]) {
int len=strlen(s), now=1, to;
mmset(used, false); ed=0;
for(int i=0; i<len; ++i) {
to=s[i]-'a';
for(int j=1; j<=ed; ++j) {
if(stk[j]==to) break;
if(trie[now][stk[j]])
return false;
}
if(!used[to]) used[to]=1, stk[++ed]=to;
now=trie[now][to];
if(flg[now] && i!=len-1) // another string is current string @p s[]'s prefix
return false;
}
return true;
}
} // using namespace saya;
inline void input() {
n=readin(1);
rep(i, 1, n) {
cin>>s[i];
saya::insert(s[i].c_str());
}
}
bool yes[maxn+5];
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
input();
int cnt=0;
rep(i, 1, n) if(saya::query(s[i].c_str()))
yes[i]=1, ++cnt;
cout<<cnt<<'\n';
rep(i, 1, n) if(yes[i])
cout<<s[i]<<'\n';
return 0;
}
验证码 exnb 我也不知道啥意思......