题目描述本题要求实现一种简单的源代码压缩方法。源代码中出现的关键字共161616个见下文被替换为X形式其中XXX是关键字对应的编号000到151515。标识符由字母和数字组成中长度≥3\ge 3≥3的标识符会被编码为X其中XXX是该标识符的编号从161616开始递增。但首次出现的标识符不进行替换保留原样仅将其映射关系存入内存供后续出现时替换。长度小于333的标识符不编码。字符不会出现在原始源代码中。输入文件可能包含多组数据每组以单独一行end.结束。输入格式第一行为一个整数NNN表示数据集的个数。随后可能有一个空行然后依次是NNN个数据集。每个数据集包含若干行源代码最后一行是end.不含引号。数据集之间可能有一个空行。输出格式对于每个数据集输出压缩后的源代码其中关键字和已见过的标识符被替换为相应代码首次出现的标识符保持原样。每组输出之间以一个空行分隔。样例输入1 program Test; var n :integer; function harmonic(number :integer):real; var i :integer; result :real; begin result : 0; for i : 1 to number do begin number : number 1/i; end; harmonic : result; end; begin writeln(Get n:); readln(n); writeln(harmonic number for n: ); writeln(harmonic(n)); end.输出program Test; 0 n :integer; 14 harmonic(number :18):real; 0 i :18; result :21; 10 22 : 0; 2 i : 1 to 20 do 10 20 : 20 1/i; 1; 19 : 22; 1; 10 writeln(Get n:); readln(n); 23(19 20 2 n: ); 23(19(n)); 1.题目分析压缩算法按以下规则处理源代码关键字以下161616个关键字全部小写分别对应编号0∼150 \sim 150∼15var,end,for,then,else,case,goto,const,label,while,begin,until,repeat,downto,function,procedure。遇到这些单词时输出编号。标识符由字母和数字组成的连续字符串且不能与关键字冲突。若长度3 33则不编码直接输出原始字符串。若长度≥3\ge 3≥3则查看该标识符是否已经出现过即是否在映射表中。若已出现过则输出编号编号从161616开始递增。若首次出现则输出原始字符串并将该标识符与一个递增编号从161616开始存入映射表。其他字符如标点符号、空格、数字、运算符等原样输出。注意标识符可能包含数字例如number33应整体作为一个标识符处理。字符不会出现在源文件中因此不需要转义。解题思路预处理读取数据集个数NNN忽略可能存在的空行。逐行处理对于每个数据集使用getline循环读取每一行直到读到end.为止。对于每一行按字符扫描若当前字符是字母或数字则开始收集一个连续的单词标识符或关键字。收集完毕后检查该单词是否在关键字映射表中若是关键字输出编号。否则检查是否全由字母和数字组成代码中进行了校验并判断长度长度3 33直接输出原单词。长度≥3\ge 3≥3查询标识符映射表vars若存在则输出编号若不存在则将其加入映射表编号递增并输出原单词。若当前字符不是字母或数字则直接输出该字符。注意处理行末换行输出完当前行后输出一个换行符。数据集结束读入end.时不进行压缩处理因为end是关键字但end.中的end应被替换为1而点号.原样保留代码中直接输出1.并结束该数据集。输出格式每组数据压缩后若还有下一组则输出一个空行分隔。复杂度分析设源代码总字符数为LLL标识符总数为KKKK≤2000K \le 2000K≤2000。每个字符处理一次每次查找关键字或标识符使用map\texttt{map}map的O(log⁡16)O(\log 16)O(log16)或O(log⁡K)O(\log K)O(logK)总时间复杂度O(Llog⁡K)O(L \log K)O(LlogK)。空间复杂度O(K)O(K)O(K)用于存储标识符映射。代码实现// Compression// UVa ID: 625// Verdict: Accepted// Submission Date: 2016-08-16// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);mapstring,intkeywords{{var,0},{end,1},{for,2},{then,3},{else,4},{case,5},{goto,6},{const,7},{label,8},{while,9},{begin,10},{until,11},{repeat,12},{downto,13},{function,14},{procedure,15}};for(intc1;ccases;c){if(c1)cout\n;getline(cin,line);mapstring,intvars;intcount16;while(getline(cin,line),line!end.){inti0;while(iline.length()){if(isalpha(line[i])||isdigit(line[i])){string block;while(iline.length()(isalpha(line[i])||isdigit(line[i]))){blockline[i];i;}if(keywords.find(block)!keywords.end())coutkeywords[block];else{boolalphanumerictrue;for(intj0;jblock.length();j)if(!isalpha(block[j])!isdigit(block[j])){alphanumericfalse;break;}if(alphanumeric){if(block.length()3)coutblock;else{if(vars.find(block)!vars.end())coutvars[block];else{vars[block]count;coutblock;}}}elsecoutblock;}}elsecoutline[i];}cout\n;}cout1.\n;}return0;}总结本题通过扫描源代码并按规则处理单词实现了简单的压缩。关键在于正确区分关键字和标识符并处理好首次出现与后续出现的替换规则。注意标识符长度小于333时不编码。保持源代码中的空格、标点等非字母数字字符原样输出。注意数据集的结束标记end.其中end需替换为1。该题是字符串处理的典型应用考察了对输入格式的理解和逐字符解析的能力。