e619 - 00353 - Pesky Palindromes
題目描述
題目要求計算給定字串中，不重複迴文子字串的數量。迴文子字串是指字串中連續的字元序列，從左到右讀和從右到左讀相同。
解題思路
程式使用暴力法來尋找所有可能的子字串，並檢查每個子字串是否為迴文。使用一個 map 來儲存找到的迴文子字串，並記錄每個迴文子字串出現的次數。由於題目要求計算不重複的迴文子字串數量，因此只計算第一次出現的迴文子字串。
程式首先讀取輸入字串。然後，使用兩層迴圈遍歷所有可能的子字串。對於每個子字串，程式檢查它是否為迴文。如果它是迴文，則將其添加到 map 中，並增加迴文子字串的計數器。最後，程式輸出迴文子字串的總數。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是字串的長度。外層迴圈和內層迴圈分別迭代 n 次，迴文檢查需要 O(n) 時間。
- 空間複雜度: O(n^2)，在最壞的情況下，
map可能需要儲存所有可能的子字串，其數量為 O(n^2)。
程式碼
#include <iostream>
#include <map>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string a;
while(cin >> a){
map <string,int> ans;
int al=a.length(),ac=0;
for(int i=0;i<al;++i){
for(int j=i;j<al;++j){
string tmp;
for(int k=i;k<=j;++k)
tmp+=a[k];
bool chat=0;
int tl=j-i+1;
for(int k=0;k<tl;++k)
if(tmp[k]!=tmp[tl-k-1])
chat=1;
if(chat)continue;
++ans[tmp];
if(ans[tmp]==1)
++ac;
}
}
cout << "The string '" << a << "' contains " << ac << " palindromes.\n";
}
}