[UVA] 10602 - Edit Nottobad

題目連結

題意:

以第一個輸入為例，
this
thin
thing
第一個輸入 this 這個字串，
可以刪除最後幾個字母後再加上幾個字母可以變成另一個字串，
像是刪除 s 後再加上 n 可以變成 thin，
然後不刪除直接加上 g 就可以變成 thing。

另一個例子，
popcorn
apple
apricote
plum
第一個輸入不能改，就是 popcorn 這個字串，
接著刪除掉 opcorn 再加上 lum 就可以變成 plum，
接著刪除 plum 再加上 apple 就可以變成 apple，
接著刪除 ple 再加上 ricote 就可以變成 apricote，

他要求的是你要加上的所有字串的總長度要最小，
最後再加上第一個輸入的字串的長度就是要輸出的數字。

例如以上兩個例子，
第一個例子 n + g 長度2
this + 2 = 6
第二個例子 lum + apple + ricote 長度14
popcorn + 14 = 21

接著要輸出每個字串的順序。

我的作法:

我是用suffix tree的方式，
將每個字串存在一棵多元樹裡面，

像這樣將每個字串存進去，
從根節點開始，
如果該節點的字元跟要存的字串的字元相同就繼續往下走，
如果不同就分支，
例如圖中的 n 就是一個分支，
'*' 表示依個字串結束，
存完後，就DFS就好囉~
輸出整個樹的全部節點的數量(不包括'*')，

--------------------------------------------------

/* 20151101
 * hanting
 * UVa 10602 - Edit Nottobad
 * C++
 * suffix tree
 */
#include <iostream>
#include <vector>
using namespace std;
struct Tree
{
    char ch;
    vector<Tree*> node;
};
vector<string> ans;
void BuildTree(Tree *root,string str);
int DFS(Tree *root,string str);
int main()
{
    int testCase;
    cin >> testCase;
    while(testCase--)
    {
        ans.clear();
        Tree *head = new Tree;
        int strN;
        cin >> strN;
        for(int i = 0; i < strN; i++)
        {
            string str;
            cin >> str;
            BuildTree(head, str);
        }
        cout << DFS(head, "")-1 << endl;
        for(int i = 0; i < ans.size(); i++)
        {
            cout << ans[i] << endl;
        }
    }
    return 0;
}
void BuildTree(Tree *root,string str)
{
    int i;
    bool New = true;
    for(i = 0; i < root->node.size(); i++)
    {
        if(root->node[i]->ch == str[0])
        {
            New = false;
            BuildTree(root->node[i], str.substr(1));
            break;
        }
    }
    if(New)//分支
    {
        Tree *NewRoot;
        root->node.push_back(NewRoot);
        root->node[root->node.size()-1] = new Tree;
        if(str.size())
        {
            root->node[root->node.size()-1]->ch = str[0];
            BuildTree(root->node[root->node.size()-1], str.substr(1));
        }
        else
        {
            root->node[root->node.size()-1]->ch = '*';
        }
    }
}
int DFS(Tree *root,string str)
{
    int cnt = 0;
    if(root->node.size())
    {
        cnt++;
        for(int i = 0; i < root->node.size(); i++)
        {
            cnt += DFS(root->node[i], str + root->node[i]->ch);
        }
    }
    else //一個字串結束
    {
        ans.push_back(str.substr(0,str.size()-1));
    }
    delete(root);
    return cnt;
}