d252 - 94北縣賽-4-字串處理問題 (String)
題目描述
題目要求讀取一個字串和一系列的指令，根據指令修改字串，並最終輸出修改後的字串。指令包括移動游標、刪除字元、交換字元、插入字元、轉換大小寫以及移動游標等操作。
解題思路
這題的核心是模擬字串的編輯過程。程式使用一個游標 n 來追蹤目前操作的位置。根據輸入的指令，程式會更新游標位置，並對字串進行相應的修改。
0: 將游標重置到字串的開頭。$: 將游標移動到字串的結尾。x: 刪除游標位置的字元。s: 交換游標位置和下一個位置的字元。i: 在游標位置插入一個字元。u: 將游標位置的字母轉換為大寫。+: 將游標向右移動一個位置。-: 將游標向左移動一個位置。
程式使用一個 while 迴圈讀取指令，並根據指令執行相應的操作。每次修改字串後，更新字串的長度 al。
複雜度分析
- 時間複雜度: O(m * k)，其中 m 是指令的長度，k 是字串的長度。最壞情況下，每個指令可能需要遍歷整個字串（例如插入操作）。
- 空間複雜度: O(k)，其中 k 是字串的長度。程式需要儲存修改後的字串。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a,b;
while(getline(cin,a)){
int n=0;
getline(cin,b);
for(int i=0,bl=b.length(),al=a.length();i<bl;i++){
if(b[i]=='0')
n=0;
else if(b[i]=='$'){
n=al;
}
else if(b[i]=='x'&&n!=al){
string c;
for(int ii=0;ii<al;ii++)
if(ii!=n)
c+=a[ii];
a=c;
al=a.length();
}
else if(b[i]=='s'&&n!=al&&n!=al-1){
a[n]^=a[n+1];
a[n+1]^=a[n];
a[n]^=a[n+1];
}
else if(b[i]=='i'){
i++;
string c;
for(int ii=0;ii<al;ii++){
if(ii==n)
c+=b[i];
c+=a[ii];
}
n++;
a=c;
al=a.length();
}
else if(b[i]=='u'){
if(a[n]<='z'&&a[n]>='a')
a[n]-=32;
n++;
}
else if(b[i]=='+'){
n++;
}
else if(b[i]=='-'){
n--;
}
}
cout << a << "\n";
}
}