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.

Owner

yangl1996 commented Jan 4, 2015

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