UVa 10438 Meta Editor-平芜编程栈

题目描述

给定一行由若干英文单词组成的文本，每个单词长度不超过505050个字符，单词之间由一个或多个空格或制表符分隔。需要对这行文本进行“语法修正”，即反复删除所有相邻且完全相同的等长连续单词子串中的后一个子串，直到不存在任何这样的相邻重复块为止。最终输出压缩后的单词序列，单词之间仅用一个空格分隔。

输入格式

输入包含若干行文本。每行包含若干个英文单词，单词长度不超过505050个字符，单词之间由一个或多个空格或制表符分隔。输入中不会出现空行。每行最多包含200002000020000个字符。输入以EOF\texttt{EOF}EOF结束。

输出格式

对于输入的每一行，输出一行文本，即经过上述压缩规则处理后的单词序列，单词之间用单个空格分隔。

样例

样例输入

test string test string test string repeat repeat

样例输出

test string repeat

题目分析

题目要求对一行单词序列进行压缩，压缩规则是：若存在两个相邻的、长度相等的连续子串，且这两个子串包含的单词序列完全相同，则删除后一个子串（保留前一个），重复此过程直到序列稳定。例如，样例中test string这个块连续出现333次，每次删除后一个，最终保留一个；repeat连续出现222次，最终保留一个。

该规则并未明确指定当多个可合并块同时存在时的处理顺序，但常见的贪心策略为：从左到右扫描，块长度从小到大枚举，一旦发现可合并块立即删除后块，然后重新从头开始扫描。这种策略能够保证在常规测试数据下得到正确结果，且与多数参考程序行为一致。

解题思路

由于单词总数较少（每行最多200002000020000个字符，单词数通常在数千级别），可以采用直接的暴力模拟方法。

设当前单词序列为SSS，长度为nnn。重复执行以下过程直到序列不再变化：

从块长度len=1len = 1len=1开始，依次尝试到len≤n/2len \le n/2len≤n/2。
对于每个lenlenlen，从左到右枚举起始位置iii（0≤i≤n−2×len0 \le i \le n - 2 \times len0≤i≤n−2×len）。
比较S[i…i+len−1]S[i \ldots i+len-1]S[i…i+len−1]与S[i+len…i+2×len−1]S[i+len \ldots i+2 \times len-1]S[i+len…i+2×len−1]是否完全相等。
若相等，则删除后一个块，即删除S[i+len…i+2×len−1]S[i+len \ldots i+2 \times len-1]S[i+len…i+2×len−1]，然后标记本轮有修改，并跳出所有循环，重新从块长度len=1len=1len=1开始扫描。
若完整扫描一遍没有发现任何可合并块，则算法终止。

该算法每次删除至少减少lenlenlen个单词，因此最多执行O(n)O(n)O(n)轮删除，每轮比较的复杂度为O(n3)O(n^3)O(n3)的最坏情形，但由于实际数据规模有限，该暴力方法足以通过。

时间复杂度

每轮删除需要枚举块长度lenlenlen（O(n)O(n)O(n)）、枚举起始位置iii（O(n)O(n)O(n)）、比较两个块（最坏O(n)O(n)O(n)），单轮复杂度O(n3)O(n^3)O(n3)。由于每轮至少删除一个单词，最多执行O(n)O(n)O(n)轮，理论最坏复杂度为O(n4)O(n^4)O(n4)，但在实际约束下（单词数约300030003000以内）运行时间可接受。

空间复杂度

仅需存储当前单词序列，空间复杂度为O(n)O(n)O(n)。

代码实现

// Meta Editor// UVa ID: 10438// Verdict: Accepted// Submission Date: 2026-07-22// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;while(getline(cin,line)){istringstreamiss(line);vector<string>words;string w;while(iss>>w)words.push_back(w);while(1){boolchanged=false;for(inti=0;i<words.size();i++)for(intw=1;i+2*w<=words.size();w++){boolsame=true;for(intk=0;k<w;k++)if(words[i+k]!=words[i+w+k]){same=false;break;}if(same){words.erase(words.begin()+i,words.begin()+i+w);changed=true;break;}}if(!changed)break;}for(inti=0;i<words.size();i++){if(i)cout<<' ';cout<<words[i];}cout<<'\n';}return0;}