Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
最短歧义串
#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;
}
@yangl1996

This comment has been minimized.

Show comment
Hide comment
Owner

yangl1996 commented Jan 4, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment