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
*/