b500 - 子字串集合

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個字串 S，要求找出 S 的所有子字串，並將這些子字串按照字典順序輸出，但不包含空字串。

解題思路

此題採用暴力法。外層迴圈遍歷子字串的起始位置，內層迴圈遍歷子字串的結束位置。每次迭代中，將從起始位置到結束位置的字串添加到一個集合 (set) 中。使用 set 的原因是它可以自動去除重複的子字串，並且按照字典順序排序。最後，遍歷 set 並輸出其中的所有字串。

複雜度分析

• 時間複雜度: O(n^2 * m) 其中 n 是字串 S 的長度，m 是子字串的平均長度。外層迴圈 O(n)，內層迴圈 O(n)，set 的 insert 操作平均時間複雜度為 O(m)，因此總時間複雜度為 O(n^2 * m)。
• 空間複雜度: O(n^2) 最壞情況下，字串 S 的所有子字串都不同，因此 set 需要存儲 O(n^2) 個字串。

程式碼

#include <iostream>
#include <set>
using namespace std;
string s;
set <string> st;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> s;
	for(int i=0;i<s.length();++i){
		string tmp;
		for(int j=i;j<s.length();++j){
			tmp+=s[j];
			st.insert(tmp);
		}
	}
	for(auto i:st){
		cout << i << "\n";
	}
}