UVa 625 Compression-洪萨配资

题目描述

本题要求实现一种简单的源代码压缩方法。源代码中出现的关键字（共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∼15：
var,end,for,then,else,case,goto,const,label,while,begin,until,repeat,downto,function,procedure。
遇到这些单词时，输出&编号。
标识符：由字母和数字组成的连续字符串，且不能与关键字冲突。
- 若长度<3< 3<3，则不编码，直接输出原始字符串。
- 若长度≥3\ge 3≥3，则查看该标识符是否已经出现过（即是否在映射表中）。
  - 若已出现过，则输出&编号（编号从161616开始递增）。
  - 若首次出现，则输出原始字符串，并将该标识符与一个递增编号（从161616开始）存入映射表。
其他字符（如标点符号、空格、数字、运算符等）原样输出。

注意：标识符可能包含数字，例如number33，应整体作为一个标识符处理。字符&不会出现在源文件中，因此不需要转义。

解题思路

预处理：读取数据集个数NNN，忽略可能存在的空行。
逐行处理：对于每个数据集，使用getline循环读取每一行，直到读到"end."为止。对于每一行，按字符扫描：
- 若当前字符是字母或数字，则开始收集一个连续的单词（标识符或关键字）。
- 收集完毕后，检查该单词是否在关键字映射表中：
  - 若是关键字，输出&编号。
  - 否则，检查是否全由字母和数字组成（代码中进行了校验），并判断长度：
    - 长度<3< 3<3：直接输出原单词。
    - 长度≥3\ge 3≥3：查询标识符映射表（vars），若存在则输出&编号；若不存在则将其加入映射表（编号递增），并输出原单词。
- 若当前字符不是字母或数字，则直接输出该字符。
- 注意处理行末换行：输出完当前行后，输出一个换行符。
数据集结束：读入"end."时，不进行压缩处理（因为end是关键字，但end.中的end应被替换为&1，而点号.原样保留），代码中直接输出&1.并结束该数据集。
输出格式：每组数据压缩后，若还有下一组，则输出一个空行分隔。

复杂度分析

设源代码总字符数为LLL，标识符总数为KKK（K≤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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcases=stoi(line);map<string,int>keywords={{"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(intc=1;c<=cases;c++){if(c>1)cout<<'\n';getline(cin,line);map<string,int>vars;intcount=16;while(getline(cin,line),line!="end."){inti=0;while(i<line.length()){if(isalpha(line[i])||isdigit(line[i])){string block;while(i<line.length()&&(isalpha(line[i])||isdigit(line[i]))){block+=line[i];i++;}if(keywords.find(block)!=keywords.end())cout<<'&'<<keywords[block];else{boolalphanumeric=true;for(intj=0;j<block.length();j++)if(!isalpha(block[j])&&!isdigit(block[j])){alphanumeric=false;break;}if(alphanumeric){if(block.length()<3)cout<<block;else{if(vars.find(block)!=vars.end())cout<<'&'<<vars[block];else{vars[block]=count++;cout<<block;}}}elsecout<<block;}}elsecout<<line[i++];}cout<<'\n';}cout<<"&1.\n";}return0;}