資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中所有迴文子串的計數
給定一個字串 str[] 作為輸入。目標是計算 str[] 中存在的迴文子串的數量。如果兩個字串包含相同數量的字元並且所有字元都出現在兩者中，則它們互為迴文。字元的順序可以不同。
“abc” 是 “cba”、 “bca” 等的迴文。
讓我們透過示例來理解。
輸入 − str[] = “abccb”
輸出 − 迴文子串的總數為 − 4
解釋 − 迴文為 − (b,b), (c,c), (bc,cb), (bcc,ccb)
輸入 − str = “aaa”
輸出 − 迴文子串的總數為 − 4
解釋 − 迴文為 − (a,a), (a,a), (a,a), (aa,aa)
下面程式中使用的方案如下
我們使用一個包含向量的對映，其中向量包含子字串中英文字母的頻率以及陣列中此類子字串的計數。在 map<vector<int>, int> mp_vec; 中，vector<int> vec(MAX, 0) 將儲存當前子字串中所有 26 個字母的頻率。對映的整數將是具有相同頻率向量的此類子字串的計數。對於每個子字串，如果迴文的計數為 x。那麼迴文對的總數將為 x*(x-1)/2。
將字串 str[] 作為字元陣列。
函式 anagram_substring(string str, int length) 獲取字串並返回迴文子串的總數。
將初始計數設定為 0。
建立一個對映，map<vector<int>, int> mp_vec;
使用兩個 for 迴圈遍歷 str[]，從 i=0 到 i<length，以及 j=i 到 j<length。
對於每個子字串 str[i 到 j]。vector<int> vec(MAX, 0); 將包含其中英文字母的計數。
將當前字元作為 c 作為 str[j]。透過 temp=c-’a’ 獲取其整數值。
使用 vec[temp]++ 更新頻率。
使用 mp_vec[vec]++ 增加對應於此頻率向量的計數。
現在遍歷包含所有頻率向量的對映，並使用 for 迴圈從迭代器 it=mp_vec.begin() 到 it != mp_vec.end() 聚合子字串計數。
對於每個計數作為 it->second，將 ((last) * (last-1))/2 新增到所有迴文對的計數中
最後，我們將獲得所有迴文的計數。
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
int anagram_substring(string str, int length){
int count = 0;
map<vector<int>, int> mp_vec;
for (int i=0; i<length; i++){
vector<int> vec(MAX, 0);
for (int j=i; j<length; j++){
char c = str[j];
char temp = c - 'a';
vec[temp]++;
mp_vec[vec]++;
}
}
for (auto it = mp_vec.begin(); it != mp_vec.end(); it++){
int last = it->second;
count += ((last) * (last-1))/2;
}
return count;
}
int main(){
string str = "TP";
int length = str.length();
cout<<"Count of total anagram substrings are: "<<anagram_substring(str, length) << endl;
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of total anagram substrings are: 3
665 次瀏覽
