a223 - 10298 - Power Strings

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出一個給定字串 s 可以被表示為 a^n 的最大 n 值，其中 a 是一個字串，n 是一個整數。換句話說，我們要找到字串 s 中重複子字串 a 的最大重複次數，使得 s 可以由 a 重複組成。

解題思路

解題思路是尋找字串 s 的最短重複週期。程式碼的核心思想是利用一個 ans 陣列來記錄每個位置 i 處，與字串開頭的匹配長度。如果 s[i] 與 s[it] 相等，則 ans[i] 等於 it + 1，表示匹配長度增加。否則，ans[i] 為 0，並重置 it 為 0，開始新的匹配嘗試。

在計算完 ans 陣列後，程式碼檢查是否存在一個重複週期。如果 rz (第一次不匹配的位置) 大於字串長度的一半，或者字串長度不能被 rz + 1 整除，則表示字串沒有有效的重複週期，n 為 1。否則，n 等於字串長度除以 rz + 1。

複雜度分析

• 時間複雜度: O(n)，其中 n 是字串的長度。因為程式碼只需要遍歷字串一次來計算 ans 陣列。
• 空間複雜度: O(n)，因為程式碼使用了一個大小為 n 的 ans 陣列。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	string a;
	while(cin >> a){
		if(a==".")break;
		else{
			int al=a.length(),ans[al]={0},it=0,rz=0;
			for(int i=1;i<al;++i){
				if(a[i]==a[it]){
					ans[i]=it+1;
					++it;
				}
				else{
					ans[i]=0;
					rz=i;
					it=0;
				}
			}
			cout << "\n";
			if(rz>al/2||al%(rz+1)){
				cout << "1\n";
			}
			else{
				cout << al/(rz+1) << "\n";
			}
		}
	}
}