字典树。建树的过程中，一边建树一边判断有没有重复前缀的。
#include#include #include #include using namespace std;char s[1000]; int i, j, summ;struct nn{ int tot, ling, yi; }dt[50000];int main(){ int aa = 1; while (~scanf("%s", s)) { if (strcmp("9", s) == 0) break; summ = 0; int flag = 0; for (i = 0; i < 50000; i++) dt[i].ling = -1, dt[i].yi = -1, dt[i].tot = 0; int t = 0; int yy = strlen(s); for (i = 0; s[i]; i++) { int jian = 0; if (s[i] == '0') { if (dt[t].ling == -1)//建立节点 { summ++; dt[t].ling = summ; dt[summ].tot = 1; jian = 1; } t = dt[t].ling; //跳到这个节点 if ( (jian == 0 && dt[t].tot == 1 && i == yy - 1)) flag = 1; if (i == yy - 1) dt[t].tot = 5201314; } else if (s[i] == '1') { if (dt[t].yi == -1)//建立节点 { summ++; dt[t].yi = summ; dt[summ].tot = 1; jian = 1; } t = dt[t].yi;//跳到这个节点 if ( (jian == 0 && dt[t].tot == 1 && i == yy - 1)) flag = 1; if (i == yy - 1) dt[t].tot = 5201314; } } while (1) { scanf("%s", s); if (strcmp("9", s) == 0) break; int t = 0; int yy = strlen(s); for (i = 0; s[i]; i++) { int jian = 0; if (s[i] == '0') { if (dt[t].ling == -1)//建立节点 { summ++; dt[t].ling = summ; dt[summ].tot = 1; jian = 1; } t = dt[t].ling; //跳到这个节点 if (dt[t].tot == 5201314 || (jian == 0 && dt[t].tot == 1 && i == yy - 1)) flag = 1; if (i == yy - 1) dt[t].tot = 5201314; } else if (s[i] == '1') { if (dt[t].yi == -1)//建立节点 { summ++; dt[t].yi = summ; dt[summ].tot = 1; jian = 1; } t = dt[t].yi;//跳到这个节点 if (dt[t].tot == 5201314 || (jian == 0 && dt[t].tot == 1 && i == yy - 1)) flag = 1; if (i == yy - 1) dt[t].tot = 5201314; } } } if (flag == 0) printf("Set %d is immediately decodable\n", aa++); else if (flag == 1) printf("Set %d is not immediately decodable\n", aa++); } return 0;}