Problem F
Dominant Strings
Input: standard input
Output: standard output
Time Limit: 2 seconds

Given two strings s₁ and s₂, we say that s₁ dominates s₂ if the (multi)set of characters in s₁ is a proper superset of the (multi)set of characters in s₂. For instance, "acmicpc" dominates "camp", but it does not dominate "chimp" or "macpac". For a set S of strings, we call the strings in S which are not dominated by any string in S the dominant strings of S (even if they do not dominate any strings in S).

Now, your task is simply to find all the dominant strings of a set of strings.

Input

The input contains a single set of strings, with one string per line. Each string consists of at least one and at most ten lower-case alphabetic characters. There will be at most 15000 strings, and no two strings will be identical. Input is terminated by end-of-file.

Output

Output consists of all dominant strings in the input set, in alphabetical order, one word per line.

Sample Input                           Output for Sample Input

acmicpc

cccp

macpac

chimp

camp

acmicpc

chimp

macpac

Problem setter: Per Austrin, KTH

Special Thanks: Mohammad Sajjad Hossain

目明：

就如同支配一，一字串A如何支配另一字串B？可以字串A挑符出排列後成字串B。
就可以字串A支配字串B。

找出不被支配的所有字串按照字母大小排序。

解法分析：

看一下目定的件, 每字串度小等於 10。
比起 O(n*n*len) 的暴力判，我需要做法。

hint: 度小等於 10 的最多能支配多少字串？Ans. 32 (因2^5)

最情 aabbccddee, 如此一度就降低很多了。

那如何快速查找的被支配字串？使用 Trie，
建立於每字串建立 (0,0, ..., 0), 26 性的度, 它插入 Trie 中。

例如 aabb, 支配 aab, 就在 Trie 中查找 (2,1,0, ..., 0) 的所有情其除。

× aabb, bbaa 互相支配, 也不是答案。

#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
#include <queue>
using namespace std;
char s[15000][15];
int notclear[15000];
struct Node {
    Node *next[11];
    vector<int> label;
    Node() {
        label.clear();
        memset(next, 0, sizeof(next));
    }
};
void insertTrie(int str[], Node *root, int label) {
    static Node *p;
    static int i, idx;
    p = root;
    for(i = 0; i < 26; i++) {
        idx = str[i];
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
        }
        p = p->next[idx];
    }
    p->label.push_back(label);
}
void clearTrie(int str[], Node *root) {
    static Node *p;
    static int i, idx;
    p = root;
    for(i = 0; i < 26; i++) {
        idx = str[i];
        if(p->next[idx] == NULL)
            return;
        p = p->next[idx];
    }
    for(vector<int>::iterator it = p->label.begin();
        it != p->label.end(); it++)
        notclear[*it] = 1;
    p->label.clear();
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i <= 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        nd->label.clear();
        delete nd;
    }
}
int cnt[26] = {}, cnt2[26];
Node *root = new Node();
set<string> R;
void dfs(int idx, int flag) {//backtrack Dominant
    if(idx == 26) {
        if(flag)
            clearTrie(cnt2, root);
        return ;
    }
    int i;
    for(i = 0; i <= cnt[idx]; i++) {
        cnt2[idx] = i;
        dfs(idx+1, flag|(i != cnt[idx]));
    }
}
void dfsfind(Node *p) {
    int i;
    for(i = 0; i < 11; i++)
        if(p->next[i] != NULL)
            dfsfind(p->next[i]);
    if(p->label.size() == 1)
        R.insert(s[p->label[0]]);
}
int main() {
    int n = 0, i, j;
    while(gets(s[n])) {
        //strlen(s) <= 10
        memset(cnt, 0, sizeof(cnt));
        for(i = 0; s[n][i]; i++)
            cnt[s[n][i]-'a']++;
        insertTrie(cnt, root, n);
        n++;
    }
    for(i = 0; i < n; i++) {
        if(!notclear[i]) {
            memset(cnt, 0, sizeof(cnt));
            for(j = 0; s[i][j]; j++)
                cnt[s[i][j]-'a']++;
            dfs(0, 0);
        }
    }
    dfsfind(root);
    freeTrie(root);
    for(set<string>::iterator it = R.begin();
        it != R.end(); it++)
        puts((*it).c_str());
    return 0;
}
/*
acmicpc
cccp
macpac
chimp
camp
*/