http://poj.org/problem?id=3630

判断字符串间是否存在包含关系,直接在insert()函数中判断:

  1. 是否在中途找到含有末尾信息的节点
  2. 是否新建了节点
/*79ms,2416KB*/

const int maxw = 10005; /// 单词最大个数
const int maxwl = 11; /// 每个单词最大长度
const int maxnode = maxw * maxwl; /// trie树节点上限
const int sigma_size = 10; /// *随题目变化

struct Trie
{
    int next[maxnode][sigma_size]; /// next[node_id][nextchar]表示第id号节点的下一个节点对应的id号
 bool idx[maxnode];
    int sz; /// 结点总数

    void clear() { sz = 1; mem(next[0], -1); } /// 初始时只有一个根结点(空)

    /// 插入字符串s
 bool insert(const char *s)
    {
        int i, u = 0;
        char c;
        bool findnode = false, newnode = false;
        for (i = 0; s[i]; ++i)
        {
            c = s[i] & 15;
            if (next[u][c] == -1) /// 结点不存在
         {
                mem(next[sz], -1);
                idx[sz] = false; /// 中间结点的附加信息为false
             next[u][c] = sz++; /// 新建结点
             newnode = true;
            }
            u = next[u][c];
            if (idx[u]) findnode = true;
        }
        idx[u] = true; /// 字符串的最后一个字符的附加信息为true
     return !findnode && newnode;
    }
} trie;

char s[maxwl];

int main()
{
    int t, n;
    bool ok;
    SI(t);
    while (t--)
    {
        trie.clear();
        ok = true;
        SI(n), getchar();
        while (n--)
        {
            gets(s);
            if (ok) ok = trie.insert(s);
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

Comments

comments powered by Disqus