c929 - 蝸牛老師的點名單-續
題目描述
題目要求從一個包含多個名字的字串中，將這些名字分割成一行一行輸出。名字之間由一個特定的分隔字串連接。
解題思路
這題的核心是找到分隔字串，並利用它將點名單分割成獨立的名字。程式碼使用貪婪演算法，從點名單中尋找分隔字串的開頭，然後比較分隔字串和點名單的子字串，如果匹配，則將匹配的部分移除，並輸出名字。如果沒有匹配，則將點名單的字元添加到結果字串中。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是點名單的長度，m 是分隔字串的長度。最壞情況下，需要遍歷點名單的所有字元，並在每個字元處進行分隔字串的比較。
- 空間複雜度: O(n)，其中 n 是點名單的長度。空間主要用於儲存結果字串。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a;
while(getline(cin,a)){
string b,c;
getline(cin,b);
int bl=b.length(),k,al=a.length();
for(int i=0;i<bl;i++){
if(a[0]==b[i]){
k=0;
int j=i;
while(a[k]==b[j]){
j++;
k++;
}
if(k==al){
cout << c << "\n";
i+=al-1;
c.clear();
}
else
c+=b[i];
}
else
c+=b[i];
}
cout << c << "\n" ;
}
}