b001 - K-間隔 (K-GAP) 子字串
題目描述
題目要求在給定的字串中找出 K-Gap 子字串的數量。K-Gap 子字串的定義是 UVU 格式，其中 U 不為空，V 的長度為 K。
解題思路
程式碼使用暴力法來尋找 K-Gap 子字串。外層迴圈遍歷字串的起始位置 i。內層迴圈從 i 開始，嘗試建立 UVU 格式的子字串，其中 V 的長度為 K。具體來說，tmp 儲存 U 的部分，然後從 i + K + 1 開始，嘗試找到與 tmp 相同的另一個 U。如果找到相同的 U，則計數器 ans 增加。
複雜度分析
- 時間複雜度: O(n^3) (三重迴圈，其中 n 是字串的長度)
- 空間複雜度: O(n) (tmp 和 tt 字串最長可能達到 n 的長度)
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
string a;
while(cin >> n >> a){
int al=a.length(),ans=0;
for(int i=0;i<al;++i){
string tmp;
for(int j=i;j+n+1<al;++j){
tmp+=a[j];
string tt;
for(int k=j+n+1,c=0+i;k<al&&c<=j;++k,++c)
tt+=a[k];
if(tt==tmp)
++ans;
}
}
cout << ans << "\n";
}
}