b586 - 文章壓縮

🔗 前往 ZeroJudge 原題

題目描述

題目要求模擬一種文章壓縮方式。壓縮的原理是，如果讀到的單字已經存在於一個列表中，則輸出該單字在列表中的索引（從 1 開始），並將該單字移動到列表的最前方。如果讀到的單字不存在於列表中，則直接輸出該單字，並將其添加到列表的末尾。文章以 '0' 結尾。

解題思路

這題的核心是維護一個單字列表，並在讀取到新的單字時，判斷該單字是否已經存在於列表中。如果存在，則找到該單字的索引，輸出索引，並將該單字移動到列表的最前方。如果不存在，則將該單字添加到列表的末尾。

程式碼使用 vector<string> 作為單字列表。遍歷輸入字串，將連續的字母組合成單字。對於每個單字，在 vector 中搜尋。如果找到，則輸出索引，並使用 erase 和 push_back 將單字移動到列表的最前方。如果找不到，則輸出單字，並將其添加到列表的末尾。

複雜度分析

• 時間複雜度: O(n*m)，其中 n 是輸入字串的長度，m 是 vector 的最大大小。在最壞的情況下，每次讀取單字都需要遍歷整個 vector 才能找到或確定該單字是否已經存在。
• 空間複雜度: O(m)，其中 m 是 vector 的最大大小。vector 用於儲存所有出現過的單字。

程式碼

#include <iostream>
#include <vector>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	vector <string> a;
	string tmp;
	char t;
	while(t=getchar()){
		if(t=='0')break;
		if((t<='Z'&&t>='A')||(t<='z'&&t>='a'))
			tmp+=t;
		else{
			if(tmp.length()!=0){
				bool f=0;
				for(auto i=a.begin();i!=a.end();++i){
					if(*i==tmp){
						cout << a.end()-i ;
						a.erase(i);
						f=1;
						break;
					}
				}
				if(f==0)cout << tmp;
				a.push_back(tmp);
				tmp.clear();
			}
			cout << t;
		}
	}
}