地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2240
题意：对一个给定字符串，按照下面的方式编码，输出结果。
（1）连续出现的数量在 2~9 个之间的字符，用两个字符表示。第一个字符表示数量（2~9），第二个是该字符。如果连续字符数量超过 9 个，先编码前 9 个字符，然后继续编码其余部分。
（2）对于不包含连续字符的序列，先输出一个字符 1，然后是这个序列，然后结尾再追加一个字符 1。如果序列中包含字符 1，则在前面加一个转义字符 1，即输出连续两个 1。
分析：粗看此题比较简单，线性扫描一次字符串即可。扫描过程涉及到状态转换，难度不大。但必须仔细阅读题目要求，因此需要很大的细心。我提交了 5 次才通过。主要是仔细审题。代码无须解释，严格按照题目要求的编码即可。只要通过基本测试即可。下面举几个典型的例子：
aaaxyz -> 3a1xyz1
aaa817 -> 3a181171
aaaaaaaaaa -> 9a1a1
11 -> 21
1 -> 1111
aaab -> 3a1b1
下面是第 8 次提交的代码，主要变动是去掉了不必要的用于存储“不重复字符序列”的辅助空间，和一些细微调整（发现不重复序列的截止点时，直接转入重复序列状态，而不是未知状态。发现重复序列的截止点时，必须进入未知状态，因为下一个状态取决于 p[2] 和 p[1] 的关系）。把循环体内的 if - else if 改成了 switch 语句，以让逻辑更清楚。
zoj2240_code
#include <stdio.h> #define UNKNOW 0 /* 未知状态 */ #define SUBSTR 1 /* 处于 不重复字符序列 中 */ #define REPEAT 2 /* 处于 重复字符序列 中 */ /* 输出不重复字符序列中的一个字符，1 需要转义 */ void put_one_char(char c) { if(c == '1') printf("11"); else putchar(c); } void encode(char* text) { char* p = text; int status = UNKNOW; int count; /* 重复字符序列长度 */ while(*p) { switch(status) { case UNKNOW: /* 检测当前所处状态 */ if(p[1] != p[0]) { status = SUBSTR; printf("1"); /* 前缀 1 */ put_one_char(*p); } else { status = REPEAT; count = 1; } break; case SUBSTR: /* 位于 不重复字符序列 中 */ if(p[1] != p[0]) { put_one_char(*p); } else { printf("1"); /* 后缀 1 */ status = REPEAT; count = 1; } break; case REPEAT: /* 位于 重复字符序列 中 */ count++; if(count == 9 || p[1] != p[0]) { printf("%d%c", count, *p); status = UNKNOW; } break; } ++p; } /* 重要：如果以不重复字符序列结束，循环结束后输出后缀 1 */ if(status == SUBSTR) printf("1"); } int main(int argc, char* argv[]) { char line[1024]; while(gets(line) != NULL) { encode(line); printf("\n"); } return 0; }
encode 函数中，由于前两个 case 的代码比较接近，因此可以把前两个 case 合并到一起，使代码更紧凑，但可读性可能有所降低。代码如下：
code_encode_v2
void encode(char* text) { char* p = text; int status = UNKNOW; int count; /* 重复字符序列长度 */ while(*p) { switch(status) { case UNKNOW: /* 检测当前所处状态 */ case SUBSTR: /* 位于 不重复字符序列 中 */ if(p[1] != p[0]) { if(status == UNKNOW) { status = SUBSTR; printf("1"); /* 前缀 1 */ } put_one_char(*p); } else { if(status == SUBSTR) printf("1"); /* 后缀 1 */ status = REPEAT; count = 1; } break; case REPEAT: /* 位于 重复字符序列 中 */ count++; if(count == 9 || p[1] != p[0]) { printf("%d%c", count, *p); status = UNKNOW; } break; } ++p; } /* 重要：如果以不重复字符序列结束，循环结束后输出后缀 1 */ if(status == SUBSTR) printf("1"); }
代码中需要注意的几点：
（1）如果是连续出现的字符1，是不需要转义的，因为这时的 1 不会有歧义。例如“111” 被编码为“31”，而不是“311”。
（2）如果字符串以不重复序列结束，则不要遗忘输出后缀 1。遇到字符串结尾时，循环结束，但序列可能尚未输出完成！这仅存在于字符串的最后一个字符和倒数第二个字符不同的情况（如果相同，则属于连续字符序列，在循环结束之前已经输出了）。
