题目描述在MS-DOS\texttt{MS-DOS}MS-DOS和Unix\texttt{Unix}Unix系统中都存在重命名文件的命令。MS-DOS\texttt{MS-DOS}MS-DOS中使用rename而Unix\texttt{Unix}Unix中使用mv。两者的一个重要区别在于对通配符*的处理方式不同。在MS-DOS\texttt{MS-DOS}MS-DOS中可以使用如下命令renameold* new*这条命令会将所有以old开头的文件名中的old替换为new。然而在Unix\texttt{Unix}Unix中mv命令并不支持这种通配符写法。本题要求我们编写一个程序将MS-DOS\texttt{MS-DOS}MS-DOS风格的rename命令转换为一系列Unix\texttt{Unix}Unix风格的mv命令。输入格式每个数据集首先包含一个文件名列表每行一个文件名以单独一行的end结束。随后是一系列rename命令每行格式为rename wildfrom wildto其中wildfrom和wildto各包含恰好一个通配符*。命令列表以单独一行的end结束。输入中不会出现重复的文件名。输出格式对于每条rename命令首先原样输出该命令。然后输出一系列mv命令顺序与输入中文件名的出现顺序一致。每个数据集结束后输出一个空行。特殊规则本题中的*可以匹配任意数量的任意可打印字符没有MS-DOS\texttt{MS-DOS}MS-DOS中888字符或点号.的限制。大小写敏感与Unix\texttt{Unix}Unix一致。文件名长度限制为141414个字符。每条rename命令基于原始的文件名列表执行而不是上一条命令的结果。解题思路问题本质将一条形如rename A*B C*D的命令转换为若干条mv命令。对于每个匹配A*B模式的文件名需要将其转换为C*D模式。这里的A、B、C、D均为字符串可能为空*代表一个“通配符占位符”。匹配的规则是文件名以A开头以B结尾中间的部分即*匹配的内容可以任意长度包括空串。转换后的新文件名应当为C 中间匹配的部分 D。核心难点如何匹配*所对应的子串给定一个模式from例如abFile*.c和一个文件名例如abFile001.c我们需要找出*所匹配的具体内容。模式分解模式from中包含恰好一个*可以将其分解为两部分前缀*之前的所有字符后缀*之后的所有字符例如abFile*.c→ 前缀abFile后缀.cac*.c→ 前缀ac后缀.c*→ 前缀空串后缀空串匹配规则对于文件名filename如果它能够匹配模式from则必须满足前缀匹配文件名开头部分必须完全等于from的前缀后缀匹配文件名结尾部分必须完全等于from的后缀前缀和后缀不能重叠前缀匹配的结尾位置必须严格小于后缀匹配的开始位置匹配完成后*所对应的内容就是文件名中位于前缀之后、后缀之前的子串。例如模式abFile*.c文件名abFile001.c前缀abFile匹配前555个字符后缀.c匹配最后222个字符中间部分为001特殊情况处理需要考虑边界情况前缀或后缀可能为空*匹配的内容可以为空例如a*匹配a中间部分为空文件名长度可能正好等于前缀长度 后缀长度此时*匹配空串算法步骤读取文件名列表将所有文件名存储到vectorstring中直到遇到end。处理每条rename命令读取command、from、to输出原始命令从to中提取firstpart*之前的部分和secondpart*之后的部分遍历所有原始文件名对每个文件名执行匹配和转换匹配和转换使用两个指针分别从前往后和从后往前扫描前向扫描比较from和filename的字符直到遇到*或不匹配后向扫描比较from和filename的末尾字符直到遇到*或不匹配验证匹配条件两个扫描都正确地在*位置停止前后扫描的区间不重叠即前缀结束位置i−1i - 1i−1必须小于后缀开始位置j1j 1j1提取中间部分filename[i..j]构造新文件名firstpart mid secondpart输出mv oldname newname正确性分析这种双向扫描方法能够正确处理各种情况当from以*开头时前缀为空前向扫描立即遇到*当from以*结尾时后缀为空后向扫描立即遇到*通过比较iii和jjj的值可以检测出前缀和后缀是否重叠即模式无法匹配的情况时间复杂度O(N×M)O(N \times M)O(N×M)其中NNN是文件名数量MMM是文件名平均长度。由于文件名长度不超过141414这个复杂度完全可以接受。代码实现// Rename// UVa ID: 282// Verdict: Accepted// Submission Date: 2016-06-06// UVa Run Time: 0.120s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string firstpart,secondpart,command,from,to;// 匹配并转换单个文件名voidmatch(stringfilename){// 前向扫描比较前缀inti0;while(ifrom.length()ifilename.length()from[i]filename[i]from[i]!*)i;// 后向扫描比较后缀intjfilename.length()-1,kfrom.length()-1;while(j0k0filename[j]from[k]from[k]!*)j--,k--;// 验证匹配条件// 1. 前向扫描必须在 * 处停止// 2. 后向扫描也必须在 * 处停止// 3. 前后扫描的区间不能重叠if(from[i]!*||from[k]!*||ij1)return;// 输出 mv 命令coutmv filename ;// 输出新文件名firstpart 中间部分 secondpartcoutfirstpart;for(intki;kj;k)coutfilename[k];coutsecondpartendl;}intmain(){ios::sync_with_stdio(false);string line;vectorstringfilenames;while(cinline){// 读取文件名列表if(line!end)filenames.push_back(line);else{// 处理 rename 命令序列while(cincommand,command!end){cinfromto;// 输出原始命令coutcommand from toendl;// 从目标模式 to 中提取 firstpart 和 secondpart// firstpart: * 之前的部分firstpart.clear();secondpart.clear();for(inti0;ito.length()to[i]!*;i)firstpartto[i];// secondpart: * 之后的部分for(intjto.length()-1;j0to[j]!*;j--)secondpart.insert(secondpart.begin(),to[j]);// 对每个原始文件名进行匹配和转换for(inti0;ifilenames.size();i)match(filenames[i]);}// 每个数据集结束后输出空行coutendl;// 清空文件名列表准备处理下一个数据集filenames.clear();}}return0;}总结本题的核心在于理解MS-DOS\texttt{MS-DOS}MS-DOS通配符*的匹配语义并将其正确转换为Unix\texttt{Unix}Unixmv命令序列。通过将模式分解为前缀和后缀并利用双向扫描确定*匹配的内容可以简洁地解决问题。代码中需要注意边界条件处理特别是当*出现在模式开头或结尾时的情况。