Skip to content

Instantly share code, notes, and snippets.

@yangl1996 yangl1996/str.cpp
Created Jan 2, 2015

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.

Copy link
Owner Author

commented Jan 4, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.