UVaOJ 644 - Immediate Decodability

1584 단어
AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume 1. Elementary Problem Solving :: String
Description
통신 중의 인코딩 방식은 모든 문자에 대응하는 이진 인코딩을 요구한다.
다른 문자에 대응하는 인코딩의 접두사일 수 없습니다.
몇 개의 인코딩 방식에 대해 실행 가능한지 확인하십시오.
Type
String
Analysis
모든 문자열이 다른 문자열의 접두사인지 판단하면 됩니다.
만약 어떤 문자열이 다른 문자열의 접두사라면 인코딩을 할 수 없습니다.
(제목이 너무 직설적이어서 제목만 다시 읽은 것 같다)
Solution
// UVaOJ 644
// Immediate Decodability
// by A Code Rabbit

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 100000;

string str[MAXN];
int top;

bool IsPrefix(string , string);

int main() {
    int cnt_case = 0;
    top = 0;
    while (cin >> str[top]) {
        if (str[top] == "9") {
            bool bo = false;
            for (int i = 0; i < top; i++)
                for (int j = 0; j < top; j++)
                    if (i != j && IsPrefix(str[i], str[j]))
                        bo = true;
            printf("Set %d is %simmediately decodable
", ++cnt_case, bo ? "not " : "");             top = 0;         } else {             top++;         }     }     return 0; } bool IsPrefix(string a, string b) {     for (int i = 0; i < a.length(); i++)         if (a[i] != b[i]) return false;     return true; }

좋은 웹페이지 즐겨찾기