#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <new>

#define MAX_DICT_WORDS  50000
#define MAX_DICT_CHARS  350000
#define MAX_WORD_LEN    20

class DictWord
{
public:
    DictWord* next;
    char *word;
};

class DictWordList
{
public:
    DictWord *head;
    int size;
    DictWordList() :head(NULL),size(0) { }
    void push(DictWord* node)
    {
        node->next = head;
        head = node;
    };
};

class Dict
{
public:
    static char allWords[MAX_DICT_CHARS + MAX_DICT_WORDS];
    DictWord words[MAX_DICT_WORDS];
    DictWordList wordOfLen[MAX_WORD_LEN];
    int nWords;
    void readDict()
    {
        int i, len;
        char *pWord = &allWords[0];
        scanf("%d", &nWords);
        for (i = 0; i < nWords; i++) {
            scanf("%s", pWord);
            len = strlen(pWord);
            words[i].word = pWord;
            wordOfLen[len].push(&words[i]);
            pWord += len + 1;
        }
    }
};
char Dict::allWords[MAX_DICT_CHARS + MAX_DICT_WORDS];

class CodeMap
{
public:
    char decodeTable[26];
    char encodeTable[26];
    
    CodeMap()
    {
        for (int i = 0; i < 26; i++) {
            decodeTable[i] = encodeTable[i] = '*';
        }
    };
    inline char decode(char cryptChar) {
        return decodeTable[cryptChar - 'A'];
    };
    inline char encode(char clearChar) {
        return encodeTable[clearChar - 'A'];
    };
    inline void setMapping(char cryptChar, char clearChar) {
        decodeTable[cryptChar - 'A'] = clearChar;
        encodeTable[clearChar - 'A'] = cryptChar;
    };
    inline void unsetMapping(char cryptChar, char clearChar) {
        decodeTable[cryptChar - 'A'] =
        encodeTable[clearChar - 'A'] = '*';
    };
};

class TextWord
{
public:
    char* str;
    int len;
};

class TextWords
{
public:
    int nWords;
    TextWord* words;
    char* textBuf;
    int bufLen;
    CodeMap map;
    int nAnswers;
    int nCalls;
    CodeMap answer1;
    Dict* dict;
    TextWords(Dict* d)
    : nWords(0), words(NULL), dict(d)
    {
        bufLen = 800;
        textBuf = (char*)malloc(bufLen * sizeof(char));
    }
    ~TextWords()
    {
        if (words)
            free(words);
        free(textBuf);
    }
    
    void readText()
    {
        int i, j, wordsInLine, textLen, prevChar, thisChar, len;
        char *lineBuf;
        enum {WORD_CHAR = 0, BLANK_CHAR = 1};

        
        lineBuf = textBuf;
        nWords = 0; textLen = 0;
        do {
            if (bufLen - textLen < 81) {
                bufLen += 800;
                textBuf = (char*)realloc(textBuf, bufLen);
                lineBuf = textBuf + textLen;
            }
            wordsInLine = 0;
            gets(lineBuf);
            len = strlen(lineBuf);
            prevChar = BLANK_CHAR;
            for (i = 0; i < len; i++) {
                if (lineBuf[i] >= 'A' && lineBuf[i] <= 'Z') 
                    thisChar = WORD_CHAR;
                else
                    thisChar = BLANK_CHAR;
                if (prevChar == BLANK_CHAR && thisChar == WORD_CHAR) {
                    wordsInLine++;
                }
                prevChar = thisChar;
            }
            nWords += wordsInLine;
            // to avoid "joining last word of this line and first word of next line"
            lineBuf[len] = ' ';
            lineBuf += len + 1;
            textLen += len + 1;
        } while ((wordsInLine > 0) && !feof(stdin));
        
         words = (TextWord*)malloc(nWords * sizeof(TextWord));
         prevChar = BLANK_CHAR;
         j = 0;
         for (i = 0; i < textLen; i++) {
            if (textBuf[i] >= 'A' && textBuf[i] <= 'Z') 
                thisChar = WORD_CHAR;
            else
                thisChar = BLANK_CHAR;
            if (prevChar == BLANK_CHAR && thisChar == WORD_CHAR) {
                words[j].str = textBuf + i;
            } else if (prevChar == WORD_CHAR && thisChar == BLANK_CHAR) {
                textBuf[i] = '\0';
                words[j].len = textBuf + i - words[j].str;
                j++;
            }
            prevChar = thisChar;
        }
   }
    
    void sortWords()
    {
        int i, j, k, freq[26], maxF, iMaxF, f;
        bool seen[26];
        TextWord tmpW;
        // eliminate duplicate words
        for (i = nWords - 2; i >= 0 ; i--) {
            for (j = nWords - 1; j > i; j--) {
                if (strcmp(words[i].str, words[j].str) == 0) {
                    for (k = j; k < nWords - 1; k++) {
                        words[k] = words[k + 1];
                    }
                    nWords--;
                }
            }
        }
        // Choose the word that share the most large number of chars
        // with other words as the first. This should make 'conflicts'
        // between words show up early (in the iterations of tryDecode()).
        for (i = 0; i < 26; i++) {
            freq[i] = 0;
        }
        for (i = 0; i < nWords; i++) {
            for (j = 0; j < words[i].len; j++) {
                freq[words[i].str[j] - 'A']++;
            }
        }
        iMaxF = 0; maxF = 0;
        for (i = 0; i < nWords; i++) {
            f = 0;
            for (j = 0; j < words[i].len; j++) {
                f += freq[words[i].str[j] - 'A'];
            }
            if (f > maxF) {
                maxF = f;
                iMaxF = i;
            }
        }
        tmpW = words[0]; words[0] = words[iMaxF]; words[iMaxF] = tmpW;
        
        // Starting from the second wrod, we try to maximize char sharing
        // with preceeding words. This is meant to reduce branches 
        // and also to discover confilicts as early as possible.
        for (i = 0; i < 26; i++) {
            seen[i] = false;
        }
        for (k = 1; k < nWords - 1; k++) {
            for (j = 0; j < words[k].len; j++) {
                seen[words[k - 1].str[j] - 'A'] = true;
            }
            maxF = 0; iMaxF = 0;
            for (i = k; i < nWords; i++) {
                f = 0;
                for (j = 0; j < words[i].len; j++) {
                    if (seen[words[i].str[j] - 'A'])
                        f++;
                }
                if (f > maxF) {
                    maxF = f;
                    iMaxF = i;
                }
            }
            tmpW = words[k]; words[k] = words[iMaxF]; words[iMaxF] = tmpW;
        }
    };
    void innerTryDecode(int k)
    {
        DictWord* pw;
        int j;
        bool isNew[MAX_WORD_LEN];
        char dec, enc;
        
        nCalls++;
        if (k >= nWords) {
            nAnswers++;
            if (nAnswers == 1)
                answer1 = map;
            return;
        }
        
        for (pw = dict->wordOfLen[words[k].len].head; pw != NULL; pw = pw->next) {
            for (j = 0; j < words[k].len; j++)
                isNew[j] = false;
            j = 0;
            while (j < words[k].len) {
                dec = map.decode(words[k].str[j]);
                enc = map.encode(pw->word[j]);
                if (enc == '*' && dec == '*') {
                    isNew[j] = true;
                    map.setMapping(words[k].str[j], pw->word[j]);
                } else if (!(dec == pw->word[j] && enc == words[k].str[j])) {
                    // confict with current map
                    break; // while j
                }
                j++;
            }
            if (j == words[k].len) {
            // no conflicts, go decode next word in text
                innerTryDecode(k + 1);
                if (nAnswers >= 2)
                    return;
            }
            j--;
            // mapping words[k] to pw->word has been tried
            // (either it conflicts or recursive search finished),
            // undo mappings set for this word.
            while (j >= 0) {
                if (isNew[j])
                    map.unsetMapping(words[k].str[j], pw->word[j]);
                j--;
            }
        }
    };
    void tryDecode()
    {
        nAnswers = 0;
        nCalls = 0;
        new(&map) CodeMap();
        //sortWords();
        innerTryDecode(0);
        if (nAnswers == 0)
            printf("#No solution#");
        else if (nAnswers >= 2)
            printf("#More than one solution#");
        else { // one answer
            for (char c = 'A'; c <= 'Z' ; c++)
                printf("%c", answer1.encode(c));
        }
        #ifndef ONLINE_JUDGE
            printf("    %d calls", nCalls);
        #endif
        printf("\n");
    };
};


int main(int argc, char *argv[])
{
    Dict dict;
    int t;
    unsigned char c;
    
    dict.readDict();
    scanf("%d",&t);
    while (t > 0) {
        t--;
        c = ' ';
        while (! (c >= 'A' && c <= 'Z') && !feof(stdin)) {
            c = getc(stdin);
        }
        ungetc(c, stdin);
        TextWords textWords(&dict);
        textWords.readText();
        textWords.tryDecode();
    }
    return 0;
}

• bug找到了：数组长度少了1， 常见错误 -_- (60) yezonghui 2008-05-30 11:24:42
• AC了！代码已经面目全非...自己顶一个 (2) yezonghui 2008-05-30 17:00:37
  • Re:AC了！代码已经面目全非...自己顶一个 (34) sbtdkj1017 2011-09-29 22:49:44