ACM UVA 10029 (Problem C: Edit Step Ladders)

题目：

解题思路：

第一步： 根据输入建立DAG图(利用hash表进行优化)

举一个例子：
    aaa
    aba
    abah
1. 建立"aaa"的转换： "aaa", "*aa", "a*a", "aa*", "*aaa", "a*aa", "aa*a", "aaa*"。
   然后将"aaa"的所有转换放入hash表中。
2. 建立"aba"的转换： "aba", "*ba", "a*a", "ab*", "*aba", "a*ba", "ab*a", "aba*"
   然后将"aba"的所有转换放入hash表中。
3. 建立"abah"的转换(同上)
4. 在hash表中搜索"aaa"的所有转换，发现"aba"的转换中有一个和"aaa"的转换"a*a"相同，则说明"aaa"到"aba"存在一个转换。
5. 按照4的方法在hash表中搜索"aba"的所有转换。
6. 按照4的方法在hash表中搜索"abah"的所有转换。

第二步： 在建立好的DAG图中搜索最长路径。(使用DP。在搜索时使用一个表来记录从某节点开始的最常路径，这样可以稍作优化)

代码：

/*
 *******************************************************************************
 *
 * Filename: 10029.cpp
 *
 * Description:
 *
 * Version: 0.1
 * Created: 6/1/2009 11:25:47 AM
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Key {
public:
    Key(string name, int wordIndex)
    {
        this->name = name;
        this->wordIndex = wordIndex;
    }
    string name;
    int wordIndex;
};

class HashTable {
public:
    HashTable()
    {
        table.resize(400000);
    }
    void insertKey(Key* key)
    {
        int value = hash(key->name);
        table[value].push_back(key);
    }
    vector<Key*> findKeys(string keyName)
    {
        int value = hash(keyName);
        vector<Key*> keyList;
        for (int i = 0; i < table[value].size(); i++) {
            if (keyName == table[value][i]->name) {
                keyList.push_back(table[value][i]);
            }
        }
        return keyList;
    }
private:
    vector<vector<Key*> > table;
    int hash(string& keyName)
    {
        unsigned int value = 0;

        for (int i = 0; i < keyName.size(); i++) {
            value = (value << 5) + keyName[i];
        }

        return value % 400000;
    }
};

int maxPath(vector<vector<int> > &G, int v);
int main()
{
    vector<string> words;
    vector<vector<int> > G(25000);
    string tmpStr;

    cin >> tmpStr;
    while (!cin.eof()) {
        int size = words.size();
        if (size == 0 || tmpStr != words[size-1]) {
            words.push_back(tmpStr);
        }
        cin >> tmpStr;
    }

    vector< vector<Key*> > table(words.size());
    //

    // build hash table

    //

    HashTable hTable;
    for (int i = 0; i < words.size(); i++) {
        Key* key = NULL;
        // append itself
        key = new Key(words[i], i);
        hTable.insertKey(key);

        // append change
        for (int j = 0; j < words[i].size(); j++) {
            string tmpStr = words[i];
            tmpStr[j] = '*';
            key = new Key(tmpStr, i);
            hTable.insertKey(key);
            table[i].push_back(key);
        }

        // append addtion
        string tmpStr = words[i];
        tmpStr.push_back('*');
        key = new Key(tmpStr, i);
        hTable.insertKey(key);
        table[i].push_back(key);
        int starIndex = tmpStr.size() - 1;
        while (starIndex > 0) {
            tmpStr[starIndex] = tmpStr[starIndex-1];
            tmpStr[starIndex-1] = '*';
            key = new Key(tmpStr, i);
            hTable.insertKey(key);
            table[i].push_back(key);
            starIndex--;
        }
    }
    for (int i = 0; i < words.size(); i++) {
        for (int k = 0; k < table[i].size(); k++) {
            vector<Key*> keyList = hTable.findKeys(table[i][k]->name);
            for (int j = 0; j < keyList.size(); j++) {
                if (keyList[j]->wordIndex > i) {
                    G[i].push_back(keyList[j]->wordIndex);
                }
            }
        }
    }
    int maxLen = 0;
    for (int i = 0; i < words.size(); i++) {
        int len = maxPath(G, i);
        if (len > maxLen) {
            maxLen = len;
        }
    }

    cout << maxLen << endl;
}

int maxPath(vector<vector<int> > &G, int v)
{
    int retVal = 0;
    static vector<int> visitFlag(25000, 0);

    if (visitFlag[v] != 0) {
        return visitFlag[v];
    }
    for (int i = 0; i < G[v].size(); i++) {
        int len = maxPath(G, G[v][i]);
        if (len > retVal) {
            retVal = len;
        }
    }

    visitFlag[v] = retVal+1;
    return retVal+1;
}