橋杯真題解析：字符串周期性與貪心統(tǒng)計(jì)的高效解法)
1. 問題引入從一道國賽真題看字符串處理的效率陷阱最近在復(fù)盤藍(lán)橋杯的歷年國賽真題2020年第十一屆C組的“重復(fù)字符串”這道題給我留下了挺深的印象。它初看之下平平無奇甚至有點(diǎn)“送分題”的感覺不就是處理一個(gè)字符串讓它變成某個(gè)重復(fù)子串的多次連接嗎但真正動(dòng)手實(shí)現(xiàn)尤其是想在競(jìng)賽的時(shí)限和內(nèi)存限制下拿到滿分你會(huì)發(fā)現(xiàn)里面藏著好幾個(gè)關(guān)于C字符串操作、算法效率和邊界處理的經(jīng)典“坑”。很多同學(xué)止步于“暴力法能過樣例”卻不知道其算法在特定數(shù)據(jù)下會(huì)超時(shí)或者寫出了邏輯正確但冗長脆弱的代碼。這道題的核心場(chǎng)景是給定一個(gè)字符串S我們可以進(jìn)行任意次操作每次操作可以修改S中的任意一個(gè)字符。目標(biāo)是最終將S變?yōu)橐粋€(gè)“重復(fù)字符串”。所謂“重復(fù)字符串”是指存在一個(gè)長度大于等于1的子串T使得S可以由T重復(fù)K次連接而成K是大于1的整數(shù)。題目要求我們找到最少的修改次數(shù)。舉個(gè)例子字符串“abcab”。我們可以把它變成“abcabc”T“abc”,K2這需要修改最后一個(gè)字符‘b’為‘c’操作次數(shù)為1。也可以嘗試變成“ababab”T“ab”,K3但這需要修改第3個(gè)字符‘c’為‘a(chǎn)’第5個(gè)字符‘b’為‘b’不變操作次數(shù)也是1。題目就是要求這個(gè)最小的操作數(shù)。乍一看我們需要枚舉所有可能的重復(fù)單元長度len_T從1到S.length()然后檢查每個(gè)長度下將原字符串對(duì)齊到這個(gè)重復(fù)模式需要修改多少次字符最后取最小值。思路很直接但魔鬼全在細(xì)節(jié)和效率里。直接無腦枚舉和比對(duì)復(fù)雜度是O(n^2)當(dāng)n達(dá)到10^5級(jí)別時(shí)必然超時(shí)。這就需要我們深入思考字符串的周期性特征并設(shè)計(jì)高效的統(tǒng)計(jì)方法。2. 核心思路拆解枚舉周期與貪心統(tǒng)計(jì)解決這個(gè)問題的關(guān)鍵在于理解“重復(fù)字符串”等價(jià)于字符串具有周期性。如果最終字符串是T重復(fù)K次那么其長度n必須是len_T的整數(shù)倍。對(duì)于原字符串S我們假設(shè)其長度為n。我們只需要枚舉所有可能的重復(fù)單元長度len其中l(wèi)en必須是n的約數(shù)。因?yàn)槿绻鹟en不能整除n那么我們無論如何修改字符都無法讓字符串長度n由長度為len的子串整數(shù)次重復(fù)構(gòu)成。因此算法框架的第一步是找出字符串長度n的所有正約數(shù)。這些約數(shù)就是候選的重復(fù)單元長度len。對(duì)于每一個(gè)候選的len我們把字符串S想象成被切分成了k n / len個(gè)塊每個(gè)塊的長度都是len。我們的目標(biāo)是修改S使得這k個(gè)塊變得完全相同。那么最少的修改次數(shù)是多少呢這里就引出了第二個(gè)關(guān)鍵點(diǎn)列優(yōu)先統(tǒng)計(jì)與多數(shù)表決。我們不能簡(jiǎn)單地逐個(gè)塊去比較那樣效率太低。一個(gè)高效的技巧是從“列”的角度來看。我們把這k個(gè)塊上下堆疊起來形成一個(gè)有l(wèi)en列、k行的矩陣。第j列j從0到len-1就包含了所有塊的第j個(gè)字符。例如S “aabbbc”,n6。假設(shè)我們枚舉len2那么k3。三個(gè)塊是“aa”,“bb”,“bc”。堆疊起來第0列a,b,b第1列a,b,c對(duì)于每一列我們的目標(biāo)是讓這一列的所有字符都變成同一個(gè)字符因?yàn)橹挥羞@樣最終每個(gè)塊在這一位置上的字符才相同。那么對(duì)于第j列最少需要修改多少次呢答案是將該列修改為出現(xiàn)次數(shù)最多的那個(gè)字符。假設(shè)該列有k個(gè)字符其中出現(xiàn)次數(shù)最多的字符出現(xiàn)了max_count次那么這一列最少需要修改的次數(shù)就是k - max_count把非主流的字符改成主流的。所以對(duì)于給定的len總的最少修改次數(shù)就是所有l(wèi)en列的這個(gè)值(k - max_count)的總和。我們遍歷所有列累加這個(gè)值就得到了在這個(gè)重復(fù)單元長度下的最小操作數(shù)。最后對(duì)所有合法的len計(jì)算出的操作數(shù)取最小值就是全局答案。這個(gè)思路的精妙之處在于它將一個(gè)看似復(fù)雜的“讓多個(gè)字符串相同”的問題分解為了len個(gè)獨(dú)立的、簡(jiǎn)單的“讓一組字符相同”的子問題并且每個(gè)子問題都可以用O(k)的時(shí)間通過哈希表統(tǒng)計(jì)字符頻率來解決。整個(gè)算法的時(shí)間復(fù)雜度主要取決于1. 求所有約數(shù)2. 對(duì)每個(gè)約數(shù)len進(jìn)行l(wèi)en次字符統(tǒng)計(jì)每次統(tǒng)計(jì)涉及k個(gè)字符。2.1 復(fù)雜度分析與可行性證明設(shè)字符串長度為n。首先求n的所有約數(shù)通常使用O(sqrt(n))的枚舉方法即可。n的約數(shù)個(gè)數(shù)在10^5這個(gè)量級(jí)下不會(huì)太多通常少于200個(gè)這部分開銷很小。對(duì)于每個(gè)約數(shù)len我們需要處理len列每列處理k n/len個(gè)字符。所以處理一個(gè)約數(shù)的代價(jià)是len * k n。也就是說處理每個(gè)約數(shù)的復(fù)雜度是O(n)那么總復(fù)雜度就是O(d * n)其中d是約數(shù)個(gè)數(shù)。在最壞情況下如果n是一個(gè)高度合數(shù)d可能會(huì)比較大但即便如此對(duì)于n 10^5d通常也在100量級(jí)100 * 10^5 10^7這個(gè)計(jì)算量在C中是完全可以在1秒內(nèi)完成的藍(lán)橋杯通常1s時(shí)限。這比最原始的O(n^2)枚舉好了太多。這里有一個(gè)思維陷阱需要避免有人可能會(huì)想是不是只需要枚舉len到n/2因?yàn)橹貜?fù)單元至少出現(xiàn)兩次。是的K必須大于1所以len必須小于n。但我們的枚舉是基于n的約數(shù)約數(shù)本身就排除了len n的情況因?yàn)镵會(huì)等于1所以我們只需要枚舉n的真約數(shù)大于0且小于n的約數(shù)即可。3. 手把手實(shí)現(xiàn)從算法到健壯代碼理解了算法我們來看具體實(shí)現(xiàn)。我將代碼分成幾個(gè)函數(shù)使其邏輯清晰便于調(diào)試和講解。3.1 第一步獲取所有真約數(shù)vectorint getDivisors(int n) { vectorint divisors; // 只需遍歷到 sqrt(n)注意完全平方數(shù)的情況 for (int i 1; i * i n; i) { if (n % i 0) { divisors.push_back(i); // i 是約數(shù) if (i ! n / i i ! n) { // 避免重復(fù)和n本身 divisors.push_back(n / i); } } } // 注意我們需要的是真約數(shù)小于n的所以最后要過濾掉 n 本身如果被加進(jìn)去了 // 實(shí)際上由于我們加了 i ! n 的判斷n本身不會(huì)被加入。但為了安全可以再過濾一次。 vectorint properDivisors; for (int d : divisors) { if (d n) { properDivisors.push_back(d); } } return properDivisors; }注意這里有一個(gè)優(yōu)化點(diǎn)。我們其實(shí)不關(guān)心約數(shù)的順序但后續(xù)計(jì)算中l(wèi)en越小k就越大統(tǒng)計(jì)每列字符時(shí)循環(huán)層數(shù)可能外小內(nèi)大。不過對(duì)總復(fù)雜度影響不大。確保不遺漏任何真約數(shù)即可。3.2 第二步計(jì)算給定長度len下的最小修改次數(shù)這是核心函數(shù)。輸入字符串s和候選長度len返回使其成為重復(fù)字符串的最小操作數(shù)。int minChangesForLength(const string s, int len) { int n s.length(); int k n / len; // 重復(fù)次數(shù) int total_changes 0; // 遍歷每一列 for (int col 0; col len; col) { // 使用數(shù)組統(tǒng)計(jì)26個(gè)小寫字母的出現(xiàn)次數(shù)題目通常給定字符集 // 如果字符集更大比如ASCII可以用大小為128的數(shù)組或者用unordered_map vectorint count(26, 0); int max_count_in_col 0; // 遍歷該列的所有行即所有塊 for (int block 0; block k; block) { // 計(jì)算當(dāng)前字符在原字符串中的位置 int pos block * len col; char c s[pos]; int idx c - a; // 假設(shè)輸入都是小寫字母 count[idx]; // 實(shí)時(shí)更新當(dāng)前列的最大出現(xiàn)次數(shù) max_count_in_col max(max_count_in_col, count[idx]); } // 這一列需要修改的次數(shù) 總字符數(shù) - 最大出現(xiàn)次數(shù) total_changes (k - max_count_in_col); } return total_changes; }這段代碼清晰體現(xiàn)了“列優(yōu)先”統(tǒng)計(jì)的思想。兩層循環(huán)外層遍歷len列內(nèi)層遍歷該列的k個(gè)字符。使用一個(gè)固定大小的數(shù)組來統(tǒng)計(jì)頻率比unordered_map更快前提是字符集已知且不大如26個(gè)小寫字母。3.3 第三步主邏輯與邊界處理現(xiàn)在我們把所有部分組合起來并考慮一些邊界情況。#include iostream #include string #include vector #include algorithm #include climits // 用于INT_MAX using namespace std; // 上面兩個(gè)函數(shù) getDivisors 和 minChangesForLength 放在這里 int main() { string s; cin s; int n s.length(); // 邊界情況1如果字符串長度小于2它本身不可能成為重復(fù)字符串K1 // 但題目可能保證n2不過為了健壯性可以判斷。 if (n 2) { cout 0 endl; // 或者根據(jù)題意長度1無法操作輸出0 // 實(shí)際上對(duì)于n1不存在長度小于n的真約數(shù)我們的算法會(huì)得到答案0。 return 0; } vectorint divisors getDivisors(n); int min_changes INT_MAX; bool found false; for (int len : divisors) { // len 已經(jīng)是真約數(shù)即 1 len n int changes minChangesForLength(s, len); min_changes min(min_changes, changes); found true; } // 邊界情況2如果字符串本身已經(jīng)是一個(gè)重復(fù)字符串那么可能不需要任何修改。 // 我們的算法會(huì)枚舉所有約數(shù)包括使得 changes0 的那個(gè) len。 // 還有一種情況如果字符串所有字符都相同那么對(duì)于 len1 changes0。 // 所以 min_changes 最終會(huì)被更新為0。 // 邊界情況3如果 divisors 為空理論上n是質(zhì)數(shù)且大于1那么真約數(shù)只有1 // 那么循環(huán)不會(huì)執(zhí)行min_changes保持INT_MAX。我們需要處理。 // 實(shí)際上對(duì)于質(zhì)數(shù)n真約數(shù)只有1所以divisors不會(huì)為空。 // 但為了絕對(duì)安全 if (!found) { // 這種情況發(fā)生在 n1 時(shí)我們已經(jīng)提前處理了。 // 如果 n 是質(zhì)數(shù)divisors 會(huì)包含1。 min_changes n; // 一個(gè)保守的估計(jì)或者根據(jù)題意處理。 } cout min_changes endl; return 0; }3.4 一個(gè)完整的、優(yōu)化過的示例代碼將上述思路整合并加入一些細(xì)微優(yōu)化比如在minChangesForLength函數(shù)中如果某列修改次數(shù)已經(jīng)超過當(dāng)前全局最小值可以提前剪枝我們得到最終版本#include bits/stdc.h using namespace std; int minChangesForLength(const string s, int len, int current_min) { int n s.size(); int k n / len; int total 0; for (int col 0; col len; col) { int cnt[26] {0}; // C風(fēng)格數(shù)組更快 int max_cnt 0; for (int block 0; block k; block) { char c s[block * len col]; max_cnt max(max_cnt, cnt[c - a]); } total (k - max_cnt); // 剪枝如果當(dāng)前累計(jì)修改數(shù)已經(jīng)超過已知最小值后面就不用算了 if (total current_min) { return total; // 直接返回一個(gè)較大的值不影響min比較 } } return total; } int main() { string s; cin s; int n s.size(); int ans n; // 最壞情況每個(gè)字符都改也就是n // 枚舉所有可能的重復(fù)單元長度 len (必須是 n 的約數(shù)且 len n) for (int len 1; len n; len) { if (n % len ! 0) continue; ans min(ans, minChangesForLength(s, len, ans)); } cout ans endl; return 0; }這個(gè)版本更簡(jiǎn)潔直接將枚舉約數(shù)和計(jì)算整合在了一個(gè)循環(huán)里。ans初始化為n最壞情況然后枚舉所有可能的len1到n-1檢查是否為約數(shù)如果是則計(jì)算并更新答案。minChangesForLength函數(shù)中加入了剪枝優(yōu)化當(dāng)累計(jì)修改數(shù)已經(jīng)超過當(dāng)前最優(yōu)解時(shí)提前退出計(jì)算節(jié)省時(shí)間。4. 深入討論算法正確性證明與變種思考4.1 為什么貪心策略每列取眾數(shù)是最優(yōu)的這是一個(gè)需要想清楚的關(guān)鍵點(diǎn)。對(duì)于固定len分割后的k個(gè)塊我們的目標(biāo)是讓它們完全相同?？紤]最終相同的那個(gè)塊它在第j列有一個(gè)確定的字符設(shè)為X_j。那么原字符串中所有在第j列位置上的字符最終都必須被修改為X_j如果原本不是X_j的話。因此對(duì)于第j列無論我們選擇哪個(gè)字符作為最終的X_j需要修改的次數(shù)都是k減去該字符在列中原本出現(xiàn)的次數(shù)。為了使總修改次數(shù)最小我們自然希望每一列需要修改的次數(shù)盡可能少。那么對(duì)于單獨(dú)一列顯然選擇出現(xiàn)次數(shù)最多的那個(gè)字符作為最終的X_j能使k - max_count最小。并且各列之間的選擇是獨(dú)立的。第j列選擇字符A作為最終字符并不會(huì)影響第j1列選擇字符B。因此分別對(duì)每一列采取貪心策略選擇眾數(shù)組合起來就是全局最優(yōu)解。不存在一種方案通過讓某一列不選擇眾數(shù)來使得其他列節(jié)省更多的修改次數(shù)因?yàn)榱信c列之間沒有耦合關(guān)系。4.2 處理大寫字母或其他字符集題目通常說明字符串僅由小寫字母構(gòu)成所以我們用了cnt[26]。如果字符集擴(kuò)大比如包含大小寫字母和數(shù)字有幾種方法使用unordered_mapchar, int通用但常數(shù)時(shí)間開銷比數(shù)組大。使用更大的數(shù)組如果確認(rèn)是ASCII字符可以int cnt[128] {0};然后直接用字符作為下標(biāo)cnt[c]。使用vectorint(256, 0)類似數(shù)組。在競(jìng)賽中如果未明確說明優(yōu)先假設(shè)為小寫字母。若存疑使用unordered_map是最穩(wěn)妥的除非性能成為瓶頸。4.3 如果允許的“操作”定義不同怎么辦原題是“修改任意字符”。如果操作變成“交換任意兩個(gè)字符”或者“插入/刪除字符”問題就完全不同了。交換字符這變成了一個(gè)排列問題可能需要計(jì)算字符串的循環(huán)節(jié)或者通過統(tǒng)計(jì)字符頻率來匹配。目標(biāo)是讓字符串具有周期性且不改變字符的多重集合。插入/刪除字符這變成了編輯距離問題的一個(gè)變種或者需要?jiǎng)討B(tài)規(guī)劃來匹配一個(gè)重復(fù)模式。復(fù)雜度會(huì)顯著上升。所以審題時(shí)明確“操作”的定義至關(guān)重要。本題的“修改”操作是最簡(jiǎn)單的一種它只改變字符本身不改變字符串長度和字符的相對(duì)位置從而允許我們進(jìn)行獨(dú)立的列統(tǒng)計(jì)。4.4 性能實(shí)測(cè)與復(fù)雜度再驗(yàn)證為了確保我們的O(d * n)算法在n10^5時(shí)確實(shí)可行我們可以進(jìn)行一個(gè)思想實(shí)驗(yàn)。n的最大約數(shù)個(gè)數(shù)d(n)在10^5附近是多少一個(gè)極端例子是n83160它有超過100個(gè)約數(shù)。即使d128,128 * 100000 12,800,000也就是一千兩百萬次操作。在C中一次內(nèi)層循環(huán)操作數(shù)組索引、自增、比較通常只需要幾個(gè)時(shí)鐘周期。現(xiàn)代CPU每秒能執(zhí)行數(shù)十億次操作所以一千兩百萬次循環(huán)完全可以在幾十毫秒內(nèi)完成遠(yuǎn)低于1秒時(shí)限。在實(shí)際編碼時(shí)使用C風(fēng)格數(shù)組int cnt[26] {0};比vectorint(26,0)稍快因?yàn)樗跅Ｉ戏峙錄]有構(gòu)造函數(shù)開銷。在minChangesForLength函數(shù)中對(duì)于每一列我們都重新初始化這個(gè)數(shù)組由于長度固定為26使用memset或直接循環(huán)賦零也可以但int cnt[26] {0};的寫法在循環(huán)中每次都會(huì)重新初始化是清晰且高效的。5. 常見錯(cuò)誤與調(diào)試技巧即使思路正確實(shí)現(xiàn)時(shí)也可能踩坑。下面列舉幾個(gè)我調(diào)試時(shí)遇到過或者常見的問題5.1 下標(biāo)計(jì)算錯(cuò)誤這是最容易出錯(cuò)的地方。計(jì)算原字符串中對(duì)應(yīng)第block塊、第col列的字符位置時(shí)公式是int pos block * len col;一定要確保block從0開始到k-1結(jié)束col從0開始到len-1結(jié)束。可以寫一個(gè)簡(jiǎn)單的測(cè)試用例驗(yàn)證比如sabcdef,len2,k3。那么block0, col0 - pos0 - ‘a(chǎn)’block0, col1 - pos1 - ‘b’block1, col0 - pos2 - ‘c’block1, col1 - pos3 - ‘d’block2, col0 - pos4 - ‘e’block2, col1 - pos5 - ‘f’ 這符合我們將“abcdef”分成“ab”,“cd”,“ef”三個(gè)塊的直覺。5.2 忽略字符集假設(shè)如果題目沒說只有小寫字母而你用了c-‘a(chǎn)’作為下標(biāo)遇到大寫字母或數(shù)字就會(huì)數(shù)組越界導(dǎo)致運(yùn)行時(shí)錯(cuò)誤如段錯(cuò)誤。在不確定時(shí)要么先確認(rèn)題意要么使用unordered_map。藍(lán)橋杯題目描述通常比較嚴(yán)謹(jǐn)會(huì)說明“由小寫字母組成”。5.3 未處理len n的情況在我們的算法中l(wèi)en必須小于n因?yàn)镵要大于1。如果你在枚舉約數(shù)時(shí)不小心包含了n本身那么k n / n 1。此時(shí)對(duì)于任何一列max_count總是1因?yàn)橹挥?個(gè)字符k - max_count 0。這會(huì)導(dǎo)致計(jì)算結(jié)果為0即“不修改任何字符”但這不符合“重復(fù)字符串”的定義K1不算重復(fù)。所以必須排除len n的情況。我們的getDivisors函數(shù)通過if (i ! n)的判斷排除了它在主循環(huán)中枚舉len從1到n-1也自然排除了。5.4 初始化與重置頻率數(shù)組在minChangesForLength函數(shù)中對(duì)于每一列頻率數(shù)組必須清零。如果使用vectorint count(26, 0)它在每次循環(huán)開始時(shí)都會(huì)重新構(gòu)造并初始化為0是正確的。如果使用int count[26];然后試圖用memset(count, 0, sizeof(count));來清零要確保sizeof(count)計(jì)算正確。更推薦在循環(huán)內(nèi)直接定義int cnt[26] {0};寫法簡(jiǎn)潔且不易錯(cuò)。5.5 答案初始值最小修改次數(shù)的初始值應(yīng)該設(shè)為一個(gè)較大的數(shù)比如n最多每個(gè)字符都改一次。不能初始化為0否則min操作永遠(yuǎn)會(huì)得到0。5.6 測(cè)試用例設(shè)計(jì)自己設(shè)計(jì)幾個(gè)測(cè)試用例來驗(yàn)證程序簡(jiǎn)單情況s”aaaa”, 答案應(yīng)為0本身已是重復(fù)字符串T”a”,K4。需要修改s”abcab”, 答案應(yīng)為1如開頭所述。所有字符都不同s”abcdef”(n6)。枚舉約數(shù)1,2,3。len1: 需要把5個(gè)字符改成和第一個(gè)字符‘a(chǎn)’一樣不對(duì)對(duì)于len1每列只有一個(gè)字符max_count1總修改數(shù)0這里要小心len1意味著T是單個(gè)字符Kn。我們的算法k6只有1列。這一列有6個(gè)字符{a,b,c,d,e,f}出現(xiàn)次數(shù)最多的字符出現(xiàn)了1次所以修改次數(shù)6-15。這是合理的因?yàn)橐兂伞癮aaaaa”需要改5個(gè)字符。len2: k3。列0:{a,c,e}眾數(shù)出現(xiàn)1次修改2次列1:{b,d,f}眾數(shù)出現(xiàn)1次修改2次總計(jì)4次。len3: k2。列0:{a,d}修改1次列1:{b,e}修改1次列2:{c,f}修改1次總計(jì)3次。最小值為3。所以答案是3。可以驗(yàn)證比如變成“abcabc”(T”abc”, K2) 需要改3個(gè)字符d-a, e-b, f-c。邊界情況s”a”(n1)。根據(jù)題目定義長度1無法構(gòu)成K1的重復(fù)字符串。我們的算法中l(wèi)en從1到0循環(huán)不會(huì)執(zhí)行ans保持初始值n1。但也許題目期望輸出0需要仔細(xì)讀題。通常對(duì)于無法操作的情況輸出0是合理的因?yàn)闊o需修改就已經(jīng)… 但嚴(yán)格說不滿足條件。藍(lán)橋杯真題通常保證n 2所以這個(gè)邊界可能不會(huì)出現(xiàn)。為了健壯性可以在開頭判斷if(n2) {cout0; return 0;}。6. 從這道題延伸的算法與字符串技巧這道“重復(fù)字符串”題雖然歸類為字符串問題但它核心考察的是枚舉、約數(shù)、貪心以及問題轉(zhuǎn)化的能力。它把字符串周期性問題轉(zhuǎn)化為了列統(tǒng)計(jì)問題這是一個(gè)非常漂亮的思路。與此相關(guān)的經(jīng)典算法和技巧有KMP算法與字符串周期KMP算法中的next數(shù)組可以用來判斷一個(gè)字符串的最小循環(huán)節(jié)。如果一個(gè)長度為n的字符串S有長度為len的最小循環(huán)節(jié)那么n % len 0且len n - next[n]如果next[n] 0。對(duì)于本題我們可以利用這一點(diǎn)快速找到所有可能的周期長度嗎可以但需要注意KMP找到的是最小循環(huán)節(jié)。如果一個(gè)字符串有周期len那么len一定是最小循環(huán)節(jié)長度的倍數(shù)。所以我們可以先求出最小循環(huán)節(jié)長度min_len然后枚舉min_len的所有倍數(shù)同時(shí)是n的約數(shù)作為候選len。這可以稍微減少枚舉量但實(shí)現(xiàn)KMP本身也有開銷對(duì)于本題的數(shù)據(jù)范圍直接枚舉所有約數(shù)已經(jīng)足夠高效。前綴和與字符統(tǒng)計(jì)如果題目不是修改字符而是詢問“子串中某個(gè)字符出現(xiàn)的次數(shù)”那么前綴和技巧就派上用場(chǎng)了。我們可以預(yù)處理一個(gè)二維前綴和數(shù)組pre[i][c]表示前i個(gè)字符中字符c出現(xiàn)的次數(shù)。這樣可以在O(1)時(shí)間內(nèi)回答任何區(qū)間[l, r]內(nèi)字符c的出現(xiàn)次數(shù)。雖然本題用不上但這是處理字符串區(qū)間統(tǒng)計(jì)問題的利器。哈希與字符串快速比較如果題目要求判斷兩個(gè)子串是否相等或者判斷字符串是否有周期性字符串哈希如Rabin-Karp哈希可以在O(1)時(shí)間內(nèi)完成比較預(yù)處理O(n)。例如我們可以計(jì)算字符串S的哈希值然后判斷S是否等于T重復(fù)K次可以通過比較S的哈希值與T的哈希值經(jīng)過特定計(jì)算后的值是否相等來判斷。這在一些更復(fù)雜的字符串周期性問題中很有用?；氐竭@道藍(lán)橋杯真題它更像是一個(gè)思維體操訓(xùn)練我們將復(fù)雜問題分解、轉(zhuǎn)化并利用基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)數(shù)組高效統(tǒng)計(jì)的能力。在競(jìng)賽中遇到字符串問題先別急著上復(fù)雜的自動(dòng)機(jī)或后綴結(jié)構(gòu)想想能不能通過枚舉、貪心、前綴和等簡(jiǎn)單方法解決。往往最優(yōu)雅的解法就藏在最基礎(chǔ)的思考之中。 藍(lán)橋杯真題解析：字符串周期性與貪心統(tǒng)計(jì)的高效解法
1. 問題引入從一道國賽真題看字符串處理的效率陷阱最近在復(fù)盤藍(lán)橋杯的歷年國賽真題2020年第十一屆C組的“重復(fù)字符串”這道題給我留下了挺深的印象。它初看之下平平無奇甚至有點(diǎn)“送分題”的感覺不就是處理一個(gè)字符串讓它變成某個(gè)重復(fù)子串的多次連接嗎但真正動(dòng)手實(shí)現(xiàn)尤其是想在競(jìng)賽的時(shí)限和內(nèi)存限制下拿到滿分你會(huì)發(fā)現(xiàn)里面藏著好幾個(gè)關(guān)于C字符串操作、算法效率和邊界處理的經(jīng)典“坑”。很多同學(xué)止步于“暴力法能過樣例”卻不知道其算法在特定數(shù)據(jù)下會(huì)超時(shí)或者寫出了邏輯正確但冗長脆弱的代碼。這道題的核心場(chǎng)景是給定一個(gè)字符串S我們可以進(jìn)行任意次操作每次操作可以修改S中的任意一個(gè)字符。目標(biāo)是最終將S變?yōu)橐粋€(gè)“重復(fù)字符串”。所謂“重復(fù)字符串”是指存在一個(gè)長度大于等于1的子串T使得S可以由T重復(fù)K次連接而成K是大于1的整數(shù)。題目要求我們找到最少的修改次數(shù)。舉個(gè)例子字符串“abcab”。我們可以把它變成“abcabc”T“abc”,K2這需要修改最后一個(gè)字符‘b’為‘c’操作次數(shù)為1。也可以嘗試變成“ababab”T“ab”,K3但這需要修改第3個(gè)字符‘c’為‘a(chǎn)’第5個(gè)字符‘b’為‘b’不變操作次數(shù)也是1。題目就是要求這個(gè)最小的操作數(shù)。乍一看我們需要枚舉所有可能的重復(fù)單元長度len_T從1到S.length()然后檢查每個(gè)長度下將原字符串對(duì)齊到這個(gè)重復(fù)模式需要修改多少次字符最后取最小值。思路很直接但魔鬼全在細(xì)節(jié)和效率里。直接無腦枚舉和比對(duì)復(fù)雜度是O(n^2)當(dāng)n達(dá)到10^5級(jí)別時(shí)必然超時(shí)。這就需要我們深入思考字符串的周期性特征并設(shè)計(jì)高效的統(tǒng)計(jì)方法。2. 核心思路拆解枚舉周期與貪心統(tǒng)計(jì)解決這個(gè)問題的關(guān)鍵在于理解“重復(fù)字符串”等價(jià)于字符串具有周期性。如果最終字符串是T重復(fù)K次那么其長度n必須是len_T的整數(shù)倍。對(duì)于原字符串S我們假設(shè)其長度為n。我們只需要枚舉所有可能的重復(fù)單元長度len其中l(wèi)en必須是n的約數(shù)。因?yàn)槿绻鹟en不能整除n那么我們無論如何修改字符都無法讓字符串長度n由長度為len的子串整數(shù)次重復(fù)構(gòu)成。因此算法框架的第一步是找出字符串長度n的所有正約數(shù)。這些約數(shù)就是候選的重復(fù)單元長度len。對(duì)于每一個(gè)候選的len我們把字符串S想象成被切分成了k n / len個(gè)塊每個(gè)塊的長度都是len。我們的目標(biāo)是修改S使得這k個(gè)塊變得完全相同。那么最少的修改次數(shù)是多少呢這里就引出了第二個(gè)關(guān)鍵點(diǎn)列優(yōu)先統(tǒng)計(jì)與多數(shù)表決。我們不能簡(jiǎn)單地逐個(gè)塊去比較那樣效率太低。一個(gè)高效的技巧是從“列”的角度來看。我們把這k個(gè)塊上下堆疊起來形成一個(gè)有l(wèi)en列、k行的矩陣。第j列j從0到len-1就包含了所有塊的第j個(gè)字符。例如S “aabbbc”,n6。假設(shè)我們枚舉len2那么k3。三個(gè)塊是“aa”,“bb”,“bc”。堆疊起來第0列a,b,b第1列a,b,c對(duì)于每一列我們的目標(biāo)是讓這一列的所有字符都變成同一個(gè)字符因?yàn)橹挥羞@樣最終每個(gè)塊在這一位置上的字符才相同。那么對(duì)于第j列最少需要修改多少次呢答案是將該列修改為出現(xiàn)次數(shù)最多的那個(gè)字符。假設(shè)該列有k個(gè)字符其中出現(xiàn)次數(shù)最多的字符出現(xiàn)了max_count次那么這一列最少需要修改的次數(shù)就是k - max_count把非主流的字符改成主流的。所以對(duì)于給定的len總的最少修改次數(shù)就是所有l(wèi)en列的這個(gè)值(k - max_count)的總和。我們遍歷所有列累加這個(gè)值就得到了在這個(gè)重復(fù)單元長度下的最小操作數(shù)。最后對(duì)所有合法的len計(jì)算出的操作數(shù)取最小值就是全局答案。這個(gè)思路的精妙之處在于它將一個(gè)看似復(fù)雜的“讓多個(gè)字符串相同”的問題分解為了len個(gè)獨(dú)立的、簡(jiǎn)單的“讓一組字符相同”的子問題并且每個(gè)子問題都可以用O(k)的時(shí)間通過哈希表統(tǒng)計(jì)字符頻率來解決。整個(gè)算法的時(shí)間復(fù)雜度主要取決于1. 求所有約數(shù)2. 對(duì)每個(gè)約數(shù)len進(jìn)行l(wèi)en次字符統(tǒng)計(jì)每次統(tǒng)計(jì)涉及k個(gè)字符。2.1 復(fù)雜度分析與可行性證明設(shè)字符串長度為n。首先求n的所有約數(shù)通常使用O(sqrt(n))的枚舉方法即可。n的約數(shù)個(gè)數(shù)在10^5這個(gè)量級(jí)下不會(huì)太多通常少于200個(gè)這部分開銷很小。對(duì)于每個(gè)約數(shù)len我們需要處理len列每列處理k n/len個(gè)字符。所以處理一個(gè)約數(shù)的代價(jià)是len * k n。也就是說處理每個(gè)約數(shù)的復(fù)雜度是O(n)那么總復(fù)雜度就是O(d * n)其中d是約數(shù)個(gè)數(shù)。在最壞情況下如果n是一個(gè)高度合數(shù)d可能會(huì)比較大但即便如此對(duì)于n 10^5d通常也在100量級(jí)100 * 10^5 10^7這個(gè)計(jì)算量在C中是完全可以在1秒內(nèi)完成的藍(lán)橋杯通常1s時(shí)限。這比最原始的O(n^2)枚舉好了太多。這里有一個(gè)思維陷阱需要避免有人可能會(huì)想是不是只需要枚舉len到n/2因?yàn)橹貜?fù)單元至少出現(xiàn)兩次。是的K必須大于1所以len必須小于n。但我們的枚舉是基于n的約數(shù)約數(shù)本身就排除了len n的情況因?yàn)镵會(huì)等于1所以我們只需要枚舉n的真約數(shù)大于0且小于n的約數(shù)即可。3. 手把手實(shí)現(xiàn)從算法到健壯代碼理解了算法我們來看具體實(shí)現(xiàn)。我將代碼分成幾個(gè)函數(shù)使其邏輯清晰便于調(diào)試和講解。3.1 第一步獲取所有真約數(shù)vectorint getDivisors(int n) { vectorint divisors; // 只需遍歷到 sqrt(n)注意完全平方數(shù)的情況 for (int i 1; i * i n; i) { if (n % i 0) { divisors.push_back(i); // i 是約數(shù) if (i ! n / i i ! n) { // 避免重復(fù)和n本身 divisors.push_back(n / i); } } } // 注意我們需要的是真約數(shù)小于n的所以最后要過濾掉 n 本身如果被加進(jìn)去了 // 實(shí)際上由于我們加了 i ! n 的判斷n本身不會(huì)被加入。但為了安全可以再過濾一次。 vectorint properDivisors; for (int d : divisors) { if (d n) { properDivisors.push_back(d); } } return properDivisors; }注意這里有一個(gè)優(yōu)化點(diǎn)。我們其實(shí)不關(guān)心約數(shù)的順序但后續(xù)計(jì)算中l(wèi)en越小k就越大統(tǒng)計(jì)每列字符時(shí)循環(huán)層數(shù)可能外小內(nèi)大。不過對(duì)總復(fù)雜度影響不大。確保不遺漏任何真約數(shù)即可。3.2 第二步計(jì)算給定長度len下的最小修改次數(shù)這是核心函數(shù)。輸入字符串s和候選長度len返回使其成為重復(fù)字符串的最小操作數(shù)。int minChangesForLength(const string s, int len) { int n s.length(); int k n / len; // 重復(fù)次數(shù) int total_changes 0; // 遍歷每一列 for (int col 0; col len; col) { // 使用數(shù)組統(tǒng)計(jì)26個(gè)小寫字母的出現(xiàn)次數(shù)題目通常給定字符集 // 如果字符集更大比如ASCII可以用大小為128的數(shù)組或者用unordered_map vectorint count(26, 0); int max_count_in_col 0; // 遍歷該列的所有行即所有塊 for (int block 0; block k; block) { // 計(jì)算當(dāng)前字符在原字符串中的位置 int pos block * len col; char c s[pos]; int idx c - a; // 假設(shè)輸入都是小寫字母 count[idx]; // 實(shí)時(shí)更新當(dāng)前列的最大出現(xiàn)次數(shù) max_count_in_col max(max_count_in_col, count[idx]); } // 這一列需要修改的次數(shù) 總字符數(shù) - 最大出現(xiàn)次數(shù) total_changes (k - max_count_in_col); } return total_changes; }這段代碼清晰體現(xiàn)了“列優(yōu)先”統(tǒng)計(jì)的思想。兩層循環(huán)外層遍歷len列內(nèi)層遍歷該列的k個(gè)字符。使用一個(gè)固定大小的數(shù)組來統(tǒng)計(jì)頻率比unordered_map更快前提是字符集已知且不大如26個(gè)小寫字母。3.3 第三步主邏輯與邊界處理現(xiàn)在我們把所有部分組合起來并考慮一些邊界情況。#include iostream #include string #include vector #include algorithm #include climits // 用于INT_MAX using namespace std; // 上面兩個(gè)函數(shù) getDivisors 和 minChangesForLength 放在這里 int main() { string s; cin s; int n s.length(); // 邊界情況1如果字符串長度小于2它本身不可能成為重復(fù)字符串K1 // 但題目可能保證n2不過為了健壯性可以判斷。 if (n 2) { cout 0 endl; // 或者根據(jù)題意長度1無法操作輸出0 // 實(shí)際上對(duì)于n1不存在長度小于n的真約數(shù)我們的算法會(huì)得到答案0。 return 0; } vectorint divisors getDivisors(n); int min_changes INT_MAX; bool found false; for (int len : divisors) { // len 已經(jīng)是真約數(shù)即 1 len n int changes minChangesForLength(s, len); min_changes min(min_changes, changes); found true; } // 邊界情況2如果字符串本身已經(jīng)是一個(gè)重復(fù)字符串那么可能不需要任何修改。 // 我們的算法會(huì)枚舉所有約數(shù)包括使得 changes0 的那個(gè) len。 // 還有一種情況如果字符串所有字符都相同那么對(duì)于 len1 changes0。 // 所以 min_changes 最終會(huì)被更新為0。 // 邊界情況3如果 divisors 為空理論上n是質(zhì)數(shù)且大于1那么真約數(shù)只有1 // 那么循環(huán)不會(huì)執(zhí)行min_changes保持INT_MAX。我們需要處理。 // 實(shí)際上對(duì)于質(zhì)數(shù)n真約數(shù)只有1所以divisors不會(huì)為空。 // 但為了絕對(duì)安全 if (!found) { // 這種情況發(fā)生在 n1 時(shí)我們已經(jīng)提前處理了。 // 如果 n 是質(zhì)數(shù)divisors 會(huì)包含1。 min_changes n; // 一個(gè)保守的估計(jì)或者根據(jù)題意處理。 } cout min_changes endl; return 0; }3.4 一個(gè)完整的、優(yōu)化過的示例代碼將上述思路整合并加入一些細(xì)微優(yōu)化比如在minChangesForLength函數(shù)中如果某列修改次數(shù)已經(jīng)超過當(dāng)前全局最小值可以提前剪枝我們得到最終版本#include bits/stdc.h using namespace std; int minChangesForLength(const string s, int len, int current_min) { int n s.size(); int k n / len; int total 0; for (int col 0; col len; col) { int cnt[26] {0}; // C風(fēng)格數(shù)組更快 int max_cnt 0; for (int block 0; block k; block) { char c s[block * len col]; max_cnt max(max_cnt, cnt[c - a]); } total (k - max_cnt); // 剪枝如果當(dāng)前累計(jì)修改數(shù)已經(jīng)超過已知最小值后面就不用算了 if (total current_min) { return total; // 直接返回一個(gè)較大的值不影響min比較 } } return total; } int main() { string s; cin s; int n s.size(); int ans n; // 最壞情況每個(gè)字符都改也就是n // 枚舉所有可能的重復(fù)單元長度 len (必須是 n 的約數(shù)且 len n) for (int len 1; len n; len) { if (n % len ! 0) continue; ans min(ans, minChangesForLength(s, len, ans)); } cout ans endl; return 0; }這個(gè)版本更簡(jiǎn)潔直接將枚舉約數(shù)和計(jì)算整合在了一個(gè)循環(huán)里。ans初始化為n最壞情況然后枚舉所有可能的len1到n-1檢查是否為約數(shù)如果是則計(jì)算并更新答案。minChangesForLength函數(shù)中加入了剪枝優(yōu)化當(dāng)累計(jì)修改數(shù)已經(jīng)超過當(dāng)前最優(yōu)解時(shí)提前退出計(jì)算節(jié)省時(shí)間。4. 深入討論算法正確性證明與變種思考4.1 為什么貪心策略每列取眾數(shù)是最優(yōu)的這是一個(gè)需要想清楚的關(guān)鍵點(diǎn)。對(duì)于固定len分割后的k個(gè)塊我們的目標(biāo)是讓它們完全相同?？紤]最終相同的那個(gè)塊它在第j列有一個(gè)確定的字符設(shè)為X_j。那么原字符串中所有在第j列位置上的字符最終都必須被修改為X_j如果原本不是X_j的話。因此對(duì)于第j列無論我們選擇哪個(gè)字符作為最終的X_j需要修改的次數(shù)都是k減去該字符在列中原本出現(xiàn)的次數(shù)。為了使總修改次數(shù)最小我們自然希望每一列需要修改的次數(shù)盡可能少。那么對(duì)于單獨(dú)一列顯然選擇出現(xiàn)次數(shù)最多的那個(gè)字符作為最終的X_j能使k - max_count最小。并且各列之間的選擇是獨(dú)立的。第j列選擇字符A作為最終字符并不會(huì)影響第j1列選擇字符B。因此分別對(duì)每一列采取貪心策略選擇眾數(shù)組合起來就是全局最優(yōu)解。不存在一種方案通過讓某一列不選擇眾數(shù)來使得其他列節(jié)省更多的修改次數(shù)因?yàn)榱信c列之間沒有耦合關(guān)系。4.2 處理大寫字母或其他字符集題目通常說明字符串僅由小寫字母構(gòu)成所以我們用了cnt[26]。如果字符集擴(kuò)大比如包含大小寫字母和數(shù)字有幾種方法使用unordered_mapchar, int通用但常數(shù)時(shí)間開銷比數(shù)組大。使用更大的數(shù)組如果確認(rèn)是ASCII字符可以int cnt[128] {0};然后直接用字符作為下標(biāo)cnt[c]。使用vectorint(256, 0)類似數(shù)組。在競(jìng)賽中如果未明確說明優(yōu)先假設(shè)為小寫字母。若存疑使用unordered_map是最穩(wěn)妥的除非性能成為瓶頸。4.3 如果允許的“操作”定義不同怎么辦原題是“修改任意字符”。如果操作變成“交換任意兩個(gè)字符”或者“插入/刪除字符”問題就完全不同了。交換字符這變成了一個(gè)排列問題可能需要計(jì)算字符串的循環(huán)節(jié)或者通過統(tǒng)計(jì)字符頻率來匹配。目標(biāo)是讓字符串具有周期性且不改變字符的多重集合。插入/刪除字符這變成了編輯距離問題的一個(gè)變種或者需要?jiǎng)討B(tài)規(guī)劃來匹配一個(gè)重復(fù)模式。復(fù)雜度會(huì)顯著上升。所以審題時(shí)明確“操作”的定義至關(guān)重要。本題的“修改”操作是最簡(jiǎn)單的一種它只改變字符本身不改變字符串長度和字符的相對(duì)位置從而允許我們進(jìn)行獨(dú)立的列統(tǒng)計(jì)。4.4 性能實(shí)測(cè)與復(fù)雜度再驗(yàn)證為了確保我們的O(d * n)算法在n10^5時(shí)確實(shí)可行我們可以進(jìn)行一個(gè)思想實(shí)驗(yàn)。n的最大約數(shù)個(gè)數(shù)d(n)在10^5附近是多少一個(gè)極端例子是n83160它有超過100個(gè)約數(shù)。即使d128,128 * 100000 12,800,000也就是一千兩百萬次操作。在C中一次內(nèi)層循環(huán)操作數(shù)組索引、自增、比較通常只需要幾個(gè)時(shí)鐘周期。現(xiàn)代CPU每秒能執(zhí)行數(shù)十億次操作所以一千兩百萬次循環(huán)完全可以在幾十毫秒內(nèi)完成遠(yuǎn)低于1秒時(shí)限。在實(shí)際編碼時(shí)使用C風(fēng)格數(shù)組int cnt[26] {0};比vectorint(26,0)稍快因?yàn)樗跅Ｉ戏峙錄]有構(gòu)造函數(shù)開銷。在minChangesForLength函數(shù)中對(duì)于每一列我們都重新初始化這個(gè)數(shù)組由于長度固定為26使用memset或直接循環(huán)賦零也可以但int cnt[26] {0};的寫法在循環(huán)中每次都會(huì)重新初始化是清晰且高效的。5. 常見錯(cuò)誤與調(diào)試技巧即使思路正確實(shí)現(xiàn)時(shí)也可能踩坑。下面列舉幾個(gè)我調(diào)試時(shí)遇到過或者常見的問題5.1 下標(biāo)計(jì)算錯(cuò)誤這是最容易出錯(cuò)的地方。計(jì)算原字符串中對(duì)應(yīng)第block塊、第col列的字符位置時(shí)公式是int pos block * len col;一定要確保block從0開始到k-1結(jié)束col從0開始到len-1結(jié)束。可以寫一個(gè)簡(jiǎn)單的測(cè)試用例驗(yàn)證比如sabcdef,len2,k3。那么block0, col0 - pos0 - ‘a(chǎn)’block0, col1 - pos1 - ‘b’block1, col0 - pos2 - ‘c’block1, col1 - pos3 - ‘d’block2, col0 - pos4 - ‘e’block2, col1 - pos5 - ‘f’ 這符合我們將“abcdef”分成“ab”,“cd”,“ef”三個(gè)塊的直覺。5.2 忽略字符集假設(shè)如果題目沒說只有小寫字母而你用了c-‘a(chǎn)’作為下標(biāo)遇到大寫字母或數(shù)字就會(huì)數(shù)組越界導(dǎo)致運(yùn)行時(shí)錯(cuò)誤如段錯(cuò)誤。在不確定時(shí)要么先確認(rèn)題意要么使用unordered_map。藍(lán)橋杯題目描述通常比較嚴(yán)謹(jǐn)會(huì)說明“由小寫字母組成”。5.3 未處理len n的情況在我們的算法中l(wèi)en必須小于n因?yàn)镵要大于1。如果你在枚舉約數(shù)時(shí)不小心包含了n本身那么k n / n 1。此時(shí)對(duì)于任何一列max_count總是1因?yàn)橹挥?個(gè)字符k - max_count 0。這會(huì)導(dǎo)致計(jì)算結(jié)果為0即“不修改任何字符”但這不符合“重復(fù)字符串”的定義K1不算重復(fù)。所以必須排除len n的情況。我們的getDivisors函數(shù)通過if (i ! n)的判斷排除了它在主循環(huán)中枚舉len從1到n-1也自然排除了。5.4 初始化與重置頻率數(shù)組在minChangesForLength函數(shù)中對(duì)于每一列頻率數(shù)組必須清零。如果使用vectorint count(26, 0)它在每次循環(huán)開始時(shí)都會(huì)重新構(gòu)造并初始化為0是正確的。如果使用int count[26];然后試圖用memset(count, 0, sizeof(count));來清零要確保sizeof(count)計(jì)算正確。更推薦在循環(huán)內(nèi)直接定義int cnt[26] {0};寫法簡(jiǎn)潔且不易錯(cuò)。5.5 答案初始值最小修改次數(shù)的初始值應(yīng)該設(shè)為一個(gè)較大的數(shù)比如n最多每個(gè)字符都改一次。不能初始化為0否則min操作永遠(yuǎn)會(huì)得到0。5.6 測(cè)試用例設(shè)計(jì)自己設(shè)計(jì)幾個(gè)測(cè)試用例來驗(yàn)證程序簡(jiǎn)單情況s”aaaa”, 答案應(yīng)為0本身已是重復(fù)字符串T”a”,K4。需要修改s”abcab”, 答案應(yīng)為1如開頭所述。所有字符都不同s”abcdef”(n6)。枚舉約數(shù)1,2,3。len1: 需要把5個(gè)字符改成和第一個(gè)字符‘a(chǎn)’一樣不對(duì)對(duì)于len1每列只有一個(gè)字符max_count1總修改數(shù)0這里要小心len1意味著T是單個(gè)字符Kn。我們的算法k6只有1列。這一列有6個(gè)字符{a,b,c,d,e,f}出現(xiàn)次數(shù)最多的字符出現(xiàn)了1次所以修改次數(shù)6-15。這是合理的因?yàn)橐兂伞癮aaaaa”需要改5個(gè)字符。len2: k3。列0:{a,c,e}眾數(shù)出現(xiàn)1次修改2次列1:{b,d,f}眾數(shù)出現(xiàn)1次修改2次總計(jì)4次。len3: k2。列0:{a,d}修改1次列1:{b,e}修改1次列2:{c,f}修改1次總計(jì)3次。最小值為3。所以答案是3。可以驗(yàn)證比如變成“abcabc”(T”abc”, K2) 需要改3個(gè)字符d-a, e-b, f-c。邊界情況s”a”(n1)。根據(jù)題目定義長度1無法構(gòu)成K1的重復(fù)字符串。我們的算法中l(wèi)en從1到0循環(huán)不會(huì)執(zhí)行ans保持初始值n1。但也許題目期望輸出0需要仔細(xì)讀題。通常對(duì)于無法操作的情況輸出0是合理的因?yàn)闊o需修改就已經(jīng)… 但嚴(yán)格說不滿足條件。藍(lán)橋杯真題通常保證n 2所以這個(gè)邊界可能不會(huì)出現(xiàn)。為了健壯性可以在開頭判斷if(n2) {cout0; return 0;}。6. 從這道題延伸的算法與字符串技巧這道“重復(fù)字符串”題雖然歸類為字符串問題但它核心考察的是枚舉、約數(shù)、貪心以及問題轉(zhuǎn)化的能力。它把字符串周期性問題轉(zhuǎn)化為了列統(tǒng)計(jì)問題這是一個(gè)非常漂亮的思路。與此相關(guān)的經(jīng)典算法和技巧有KMP算法與字符串周期KMP算法中的next數(shù)組可以用來判斷一個(gè)字符串的最小循環(huán)節(jié)。如果一個(gè)長度為n的字符串S有長度為len的最小循環(huán)節(jié)那么n % len 0且len n - next[n]如果next[n] 0。對(duì)于本題我們可以利用這一點(diǎn)快速找到所有可能的周期長度嗎可以但需要注意KMP找到的是最小循環(huán)節(jié)。如果一個(gè)字符串有周期len那么len一定是最小循環(huán)節(jié)長度的倍數(shù)。所以我們可以先求出最小循環(huán)節(jié)長度min_len然后枚舉min_len的所有倍數(shù)同時(shí)是n的約數(shù)作為候選len。這可以稍微減少枚舉量但實(shí)現(xiàn)KMP本身也有開銷對(duì)于本題的數(shù)據(jù)范圍直接枚舉所有約數(shù)已經(jīng)足夠高效。前綴和與字符統(tǒng)計(jì)如果題目不是修改字符而是詢問“子串中某個(gè)字符出現(xiàn)的次數(shù)”那么前綴和技巧就派上用場(chǎng)了。我們可以預(yù)處理一個(gè)二維前綴和數(shù)組pre[i][c]表示前i個(gè)字符中字符c出現(xiàn)的次數(shù)。這樣可以在O(1)時(shí)間內(nèi)回答任何區(qū)間[l, r]內(nèi)字符c的出現(xiàn)次數(shù)。雖然本題用不上但這是處理字符串區(qū)間統(tǒng)計(jì)問題的利器。哈希與字符串快速比較如果題目要求判斷兩個(gè)子串是否相等或者判斷字符串是否有周期性字符串哈希如Rabin-Karp哈希可以在O(1)時(shí)間內(nèi)完成比較預(yù)處理O(n)。例如我們可以計(jì)算字符串S的哈希值然后判斷S是否等于T重復(fù)K次可以通過比較S的哈希值與T的哈希值經(jīng)過特定計(jì)算后的值是否相等來判斷。這在一些更復(fù)雜的字符串周期性問題中很有用?；氐竭@道藍(lán)橋杯真題它更像是一個(gè)思維體操訓(xùn)練我們將復(fù)雜問題分解、轉(zhuǎn)化并利用基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)數(shù)組高效統(tǒng)計(jì)的能力。在競(jìng)賽中遇到字符串問題先別急著上復(fù)雜的自動(dòng)機(jī)或后綴結(jié)構(gòu)想想能不能通過枚舉、貪心、前綴和等簡(jiǎn)單方法解決。往往最優(yōu)雅的解法就藏在最基礎(chǔ)的思考之中。