最短歧义串

str.cpp

#include <iostream>
#include <cstring>

using namespace std;

int used[200];
char dict[200][30];
int dict_scale;

char temp_ans[400];
char ans[400];

char temp[400];
char unmatched[400];
bool orig;


void search()
{
    for (int i = 0; i < dict_scale; i++)
    {
        if (used[i] == 2)
        {
            continue;
        }
        if (strcmp(unmatched, dict[i]) == 0)
        {
            if (strcmp(unmatched, temp) == 0)
            {
                continue;
            }
            orig = !orig;
            if (orig)
            {
                strcat(temp, unmatched);
                strcpy(temp_ans, temp);
                if (strlen(temp_ans) < strlen(ans))
                {
                    strcpy(ans, temp_ans);
                }
                else if (strlen(temp_ans) == strlen(ans))
                {
                    if (strcmp(temp_ans, ans) == -1)
                    {
                        strcpy(ans, temp_ans);
                    }
                }
                temp[(int)strlen(temp) - (int)strlen(unmatched)] = '\0';
            }
            else
            {
                strcpy(temp_ans, temp);
                if (strlen(temp_ans) < strlen(ans))
                {
                    strcpy(ans, temp_ans);
                }
                else if (strlen(temp_ans) == strlen(ans))
                {
                    if (strcmp(temp_ans, ans) == -1)
                    {
                        strcpy(ans, temp_ans);
                    }
                }
            }
            orig = !orig;
        }
        else if (strstr(dict[i], unmatched) == dict[i])
        {
            orig = !orig;
            used[i]++;
            char store_temp[400];
            char store_unma[400];
            strcpy(store_temp, temp);
            strcpy(store_unma, unmatched);
            if (orig)
            {
                strcat(temp, dict[i]);
            }
            strcpy(unmatched ,dict[i] + strlen(unmatched));
            search();
            strcpy(temp, store_temp);
            strcpy(unmatched, store_unma);
            orig = !orig;
            used[i]--;
        }
        else if (strstr(unmatched, dict[i]) == unmatched)
        {
            orig = !orig;
            used[i]++;
            char store_temp[400];
            char store_unma[400];
            strcpy(store_temp, temp);
            strcpy(store_unma, unmatched);
            if (orig)
            {
                strcat(temp, dict[i]);
            }
            strcpy(unmatched ,unmatched + strlen(dict[i]));
            orig = !orig;
            search();
            strcpy(temp, store_temp);
            strcpy(unmatched, store_unma);
            orig = !orig;
            used[i]--;
        }
    }
    return;
}

int main()
{
    cin >> dict_scale;
    cin.get();
    temp_ans[0] = '\0';
    memset(ans, 'a', sizeof(ans));
    ans[399] = '\0';
    for (int i = 0; i < dict_scale; i++)
    {
        cin.getline(dict[i], 30);
    }
    for (int i = 0; i < dict_scale; i++)
    {
        for (int j = 0; j < 200; j++)
        {
            used[j] = false;
        }
        orig = true;
        strcpy(temp, dict[i]);
        strcpy(unmatched, dict[i]);
        search();
    }
    cout << ans;
}

相关思路：http://blog.yangl1996.com/?p=454