e537 - 00455 - Periodic Strings

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出給定字串的最小週期 (period)。週期指的是一個子字串，通過重複這個子字串可以構成整個字串。例如，"abcabcabc" 的最小週期是 "abc"。

解題思路

程式碼採用了暴力法 (Brute Force) 的方式來尋找最小週期。對於給定的字串 a，程式碼會遍歷所有可能的子字串長度 i+1 (從 1 到字串長度)。對於每個可能的長度，程式碼會提取長度為 i+1 的子字串 b，然後檢查是否通過重複 b 可以構成整個字串 a。如果可以構成，則輸出 b 的長度，並結束搜尋。

具體來說，程式碼首先檢查字串長度是否能被子字串長度整除。如果不能整除，則說明該子字串不可能構成整個字串。如果能整除，則程式碼會將子字串重複多次，直到長度等於整個字串，然後比較重複構成的字串是否與原始字串相同。

複雜度分析

• 時間複雜度: O(n^3)，其中 n 是字串的長度。最外層迴圈遍歷 n 次，內層迴圈複製字串的次數為 n/k，比較字串需要 O(n) 的時間。
• 空間複雜度: O(n)，主要用於儲存子字串 b 和臨時字串 tmp。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n,ss=0;
	string a;
	cin >> n;
	while(n--){
		if(ss)cout << '\n';
		ss=1;
		cin >> a;
		int al=a.length(),s=0;
		string b;
		for(int i=0;i<al&&!s;++i){
			b+=a[i];
			if(al%(i+1)==0){
				string tmp;
				int t=al/(i+1);
				for(int j=0;j<t;++j){
					tmp+=b;
				}
				if(a==tmp){
					cout << b.length() << "\n";
					s=1;
				}
			}
		}
	}
}