WA #4 #8-12.
思路:对每一个字符串做判断,Diff是遍历到当前时不同的字符的个数,如果第一次出现该字母,则将该字母的优先度设为++Diff(优先度就是在自定义字母表中的顺序),然后查找该节点的兄弟节点优先度小于该节点的情况是否存在,如果存在则说明无法找到合适的顺序,否则继续,以及若该字符串是某字符串的子串也无法成为字典序最小。
样例也过了,感觉思路没什么问题,求Hack数据或思路纠正。。。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXLEN 300009
class Trie
{
public:
int next[27] = { 0 };
int time = 0;
int islast = 0;
}T[MAXLEN];
int space = 0, m, ans = 0, f[27];
string str[30007];
bool isvalid[30007], isfirst[27];
int TrieInsert(string a)
{
int len = a.size(), next = 0, index;
for (int temp = 0; temp < len; temp++)
{
index = a[temp] - 'a' + 1;
if (!T[next].next[index])T[next].next[index] = ++space;
next = T[next].next[index];
}
T[next].islast++;
return next;
}
bool TrieFirst(string a)
{
int len = a.size(), next = 0, index, diff = 0;
for (int temp = 0; temp < len; temp++)
{
index = a[temp] - 'a' + 1;
if (!isfirst[index])
{
isfirst[index] = true;
diff++;
f[index] = diff;
}
for (int t = 1; t <= 26; t++)
{
if (T[next].next[t] && f[t] < f[index])
{
return false;
}
}
if (T[next].islast)
{
return false;
}
next = T[next].next[index];
}
ans++;
return true;
}
int main()
{
cin >> m;
for (int temp = 0; temp < m; temp++)
{
cin >> str[temp];
TrieInsert(str[temp]);
}
for (int temp = 0; temp < m; temp++)
{
memset(isfirst, false, sizeof(isfirst));
memset(f, 30, sizeof(f));
isvalid[temp] = TrieFirst(str[temp]);
}
cout << ans << endl;
for (int temp = 0; temp < m; temp++)
{
if (isvalid[temp])cout << str[temp] << endl;
}
return 0;
}