11.プレフィックスコード判定

プレフィックスコード:どの文字の符号化も、同じ文字セットの別の文字の符号化のプレフィックスではありません.入力したn個の1と0からなる符号化がプレフィックス符号であるか否かを判断するプログラムを作成してください.このn個の符号化がプレフィックス符号である場合、「YES」が出力される.そうでなければ、前の符号化と矛盾する最初の符号化が出力される.入力:第1行n(以下、n行符号化を示す)第2〜n＋1行n個の0又は1からなる符号化出力:判定結果
たとえば、次のように入力します.
5 00 01 10 110 111各文字は他の文字コードのプレフィックスではないので、出力:YESを入力すると、次のようになります.
5 00 01 10 110 11符号化11と前の符号化110とのプレフィックスがあるので、出力:11
試験用例例1:入力:5 00 01 10 110 111出力:YES用例2入力:5 00 01 10 110 11出力:11用例3入力:5 00 01 10 11 111出力:111用例4入力:5 111 110 10 01 00出力:YES用例5入力:8 00 010 0110 0111 10 110 1110 1111出力:YES用例6入力:8 00 010 0110 11 11 11 1110 111出力:1110用例7 8 0110 1001 1111 1110 1010 1011 100 011出力:100用例8入力:11 11111 11100 01011 11001 10011 10101 10111 10110 1111 01100 01出力:1111
解析:0-1二叉木を1本建てて(0は左ノード、1は右ノード)、その他の方法はタイムアウトしやすい(他の方法がタイムアウトしていない場合はメッセージ共有を歓迎します).現在の入力に対して2つのタグ判定があり、1つは、現在の入力が以前に存在した列の接頭辞であり、以前に存在した列が現在の入力の接頭辞であり、この2つのいずれかが発生した場合、現在入力した列を出力してタグする.これは初めて発生したためである.

コード#コード#

#include
#include
using namespace std;

struct node
{
    unsigned int flag = 0, lson = 0, rson = 0;
}H_Tree[50000];
char str[100000];

int main()
{
    int num, StrLen;
    int TreeP, TreeNum = 2;//TreeP:point for H_Tree （ ） TreeNum:the nums of H_Tree node （ ）
    int Flag = 0;//0-YES,1-NO
    scanf("%d", &num);
    for (int i = 0; i < num; i++)
    {
        scanf("%s", str);
        if (Flag == 1) // Flag 1， 
            continue;
        StrLen = strlen(str);
        TreeP=1;// 1 ，0 
        for (int j = 0; j < StrLen; j++)
        {
            if (H_Tree[TreeP].flag == 1)// 
            {
                Flag = 1;
                printf("%s
", str);
                break;
            }

            if (j < StrLen - 1) // 
            {
                // 
                if (str[j] == '0')
                {
                    if (H_Tree[TreeP].lson == 0)// 
                    {
                        H_Tree[TreeP].lson = TreeNum;// 
                        TreeP = TreeNum++;// 
                        continue;
                    }
                    else 
                    {
                        TreeP = H_Tree[TreeP].lson;
                        continue;
                    }
                }
                // 
                else
                {
                    if (H_Tree[TreeP].rson == 0)
                    {
                        H_Tree[TreeP].rson = TreeNum;
                        TreeP = TreeNum++;
                        continue;
                    }
                    else
                    {
                        TreeP = H_Tree[TreeP].rson;
                        continue;
                    }
                }
            }
            else
            {
                if (str[j] == '0')
                {
                    if (H_Tree[TreeP].lson == 0) // 
                    {
                        H_Tree[TreeP].lson = TreeNum;
                        H_Tree[TreeNum].flag = 1;// 
                        TreeNum++;
                        continue;
                    }
                    else
                    {
                        TreeP = H_Tree[TreeP].lson;
                        if (H_Tree[TreeP].lson == 0 && H_Tree[TreeP].rson == 0)// 
                            H_Tree[TreeP].flag = 1;
                        else // 
                        {
                            Flag = 1;
                            printf("%s
", str);
                            break;
                        }
                    }
                }
                else
                {
                    if (H_Tree[TreeP].rson == 0)
                    {
                        H_Tree[TreeP].rson = TreeNum;
                        H_Tree[TreeNum].flag = 1;
                        TreeNum++;
                        continue;
                    }
                    else
                    {
                        TreeP = H_Tree[TreeP].rson;
                        if (H_Tree[TreeP].lson == 0 && H_Tree[TreeP].rson == 0)
                        {
                            H_Tree[TreeP].flag = 1;
                            break;
                        }
                        else
                        {
                            Flag = 1;
                            printf("%s
", str);
                            break;
                        }
                    }
                }
            }
        }
    }
    if (!Flag)
        printf("YES
");
    system("pause");
    return 0;
}