【UVA-213】Message Decoding【紫书】

【UVA-213】Message Decoding【紫书】

确定性有限状态自动机【DFA, Deterministic Finite Automaton】

问题链接:https://vjudge.net/problem/UVA-213

udebug链接:https://www.udebug.com/UVa/213

Solution:

这道题可以通过设计并实现一个确定性有限状态自动机来实现【使用“可以”这个词是因为,解决这道题的思路并不是只有这一种,但是使用这样的思路解决起来会比较快,并且只要在设计自动机的时候验证好它的有效性,编码出来后一般很难出现特别难以查找的bug】。大致图像如下【为了方便表述和绘图,我将一些状态合并在了一起(详细来说,对于PRELEN和DECODE,把cnt值不同的状态合并在了一起)】:

备注:逻辑上只有三个状态:LOADING【准备状态,即准备映射集,这也是系统的起始状态】、PRELEN【准备长度状态,prepare the length, 即根据三位二进制数得到接下来每个需要解码单元的长度】、DECODE【解码状态】。

接下来就是考虑实现,一种思考顺序是,逐个状态考虑,对于每个状态思考它可能接受什么输入、应当对应做什么反应。

设state变量,从左到右三个状态依次取值0, 1, 2.

对于LOADING状态,如果遇到’\n’就转移到PRELEN状态,其它输入保持本状态,并将当前输入字符加入映射集。

对于PRELEN状态,实际上可以分成四个状态:cnt分别取值0, 1, 2, 3。在实现中,我们在转移到PRELEN状态时将cnt置3,之后每一个输入就cnt–。当cnt = 0时输入了三个字符,通过判断其二进制数值【存放在变量len中】情况决定转移到LOADING还是DECODE。

对于DECODE状态,每读入len个字符【数值存储在num变量中】做一次转移判断,如果有\(num = 2^{len} – 1\),则说明其二进制各个位置都是1,根据题意,这时需要转移到PRELEN状态,其它情况则进行一次输出,之后维持在本状态。

编码的时候,我将每次循环需要执行的操作分成了两部分,上半部分进行转移条件判断,下半部分进行每种状态下执行的操作。

对于n个字符的输入,时间复杂度\(O(n)\).

#include <iostream>
#include <cstring>
// #define DBG

using namespace std;

const int LIM = 7;
const int SIZE = (1 << LIM) - 1;
char code[LIM][SIZE], in;
int state, cnt, len, num, lp, np;

inline void init() {
    memset(code, 0, sizeof code);
    num = cnt = len = state = np = 0;
    lp = 1;
}

inline void loadCode() {
    if (lp == 8) return;
    code[lp - 1][np++] = in;
    if (np == (1 << lp) - 1) {
        lp++;
        np = 0;
    }
}

int main(void) {
    init();
    while (~(in = getchar())) {
        if (state == 0 && in == '\n') {
            state = 1;
            cnt = 3;
        } else if (state == 1 && cnt == 0) {
            if (len == 0) {
                putchar('\n');
                init();
            } else {
                state = 2;
                cnt = len;
            }
        } else if (state == 2 && cnt == 0) {
            if (num == (1 << len) - 1) {
                state = 1;
                cnt = 3;
            } else {
                putchar(code[len - 1][num]);
                cnt = len;
            }
        }
#ifdef DBG
        printf("STATE-%d : in = %c\n", state, in);
#endif
        if (in == '\n') continue;
        if (state == 0) loadCode();
        if (state == 1) len = in - '0' + (cnt == 3 ? 0 : (len << 1));
        if (state == 2) num = in - '0' + (cnt == len ? 0 : (num << 1));
        if (cnt) cnt--;
    }
    return 0;
}