柚子快報(bào)邀請(qǐng)碼778899分享：算法 C++前后綴分解

http://yzkb.51969.com/

相關(guān)知識(shí)點(diǎn)

C++算法與數(shù)據(jù)結(jié)構(gòu) 打開打包代碼的方法兼述單元測試 這個(gè)算法很容易想到，學(xué)習(xí)了本文后，可以更快得想到。

前后綴分解

分治法的一種，將數(shù)組和字符串，拆分成前綴和后綴。字符串(數(shù)組）的前綴是字符串的前i個(gè)元素：s.substr(0,i-1)，即s[0]

…

\dots

… s[i-1]。同理后綴就是字符串s的后幾個(gè)元素（字符）。 不失一般型，我們以字符串s=“abcde"為例，s有5種拆分方法：

“”“abcde”“a”“bcde”“ab”“cde”“abc”“de”“abcd”“e”“abcde”“”

如果字符串的長度為n，則共有n+1中劃分法，前綴長度分別為：i

∈

\in

∈[0,n]，后綴長度分別為n-i。 一般分三步： 一，預(yù)處理前綴。 二，預(yù)處理后綴。 三，枚舉前后綴的拆分方法。

取走水果

條桌上有若干梨和蘋果，求最少取走多少水果，才能沒有蘋果在梨左邊。我們將水果分成左（前綴)、右(后綴)兩部分，前綴只有梨，取走所有蘋果；后綴只有蘋果，取走所有梨。分別枚舉前綴的長度。如下圖，初始梨蘋果梨蘋果梨，各劃分方案：紅色豎線之前是梨，紅色豎線之后是蘋果：

轉(zhuǎn)置字符串（數(shù)組)

將字符串s前后顛倒就是轉(zhuǎn)置字符串revs，兩者長度相等：

revs[i] = s [n-1-i]

字符串的前綴（后綴）就是轉(zhuǎn)置字符串的后綴（前綴)，順序相反。如："abcde"長度為3的前綴是：abcde，轉(zhuǎn)置字符串長度為3的后綴是：edcba。許多時(shí)候和順序無關(guān)，可以直接使用，如：子數(shù)組最大和、是否存在指定和的子數(shù)組、指定元素的數(shù)量。如果和順序有關(guān)，則需要轉(zhuǎn)換，比如：升序變成降序，起點(diǎn)變成終點(diǎn)。 二維數(shù)組處理起來麻煩，可以降維為一維數(shù)組后再處理。

相關(guān)題解

部分題解已經(jīng)完成，逐步發(fā)布中。

難度分【C++前后綴分解】1031. 兩個(gè)非重疊子數(shù)組的最大和1680【C++前綴和】2420. 找到所有好下標(biāo)1695【C++前后綴分解 動(dòng)態(tài)規(guī)劃】2100. 適合野炊的日子1702【C++二分查找 】1477. 找兩個(gè)和為目標(biāo)值且不重疊的子數(shù)組1850【C++前后綴分解】1653. 使字符串平衡的最少刪除次數(shù)1793【二分算法】1671：得到山形數(shù)組的最少刪除次數(shù)1912【C++前后綴分解】1888. 使二進(jìn)制字符串字符交替的最少反轉(zhuǎn)次數(shù)2005【C++前后綴分解 降維】2906. 構(gòu)造乘積矩陣2074【動(dòng)態(tài)規(guī)劃】【字符串】2167移除所有載有違禁貨物車廂所需的最少時(shí)間2219【C++前后綴分解】2484. 統(tǒng)計(jì)回文子序列數(shù)目2223【堆 優(yōu)先隊(duì)列】2163. 刪除元素后和的最小差值2225【二分查找】【雙指針】LeetCode:2565最少得分子序列2432【動(dòng)態(tài)規(guī)劃】【滑動(dòng)窗口】C++算法：3003 執(zhí)行操作后的最大分割數(shù)量3039

擴(kuò)展閱讀

我想對(duì)大家說的話工作中遇到的問題，可以按類別查閱鄙人的算法文章，請(qǐng)點(diǎn)擊《算法與數(shù)據(jù)匯總》。學(xué)習(xí)算法：按章節(jié)學(xué)習(xí)《喜缺全書算法冊(cè)》，大量的題目和測試用例，打包下載。重視操作有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適） 專注聞缺陷則喜(喜缺)是一個(gè)美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。子墨子言之：事無終始，無務(wù)多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。如果程序是一條龍，那算法就是他的是睛失敗+反思=成功 成功+反思=成功

視頻課程

先學(xué)簡單的課程，請(qǐng)移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成戰(zhàn)斗了，為老板分憂，請(qǐng)學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程 https://edu.csdn.net/lecturer/6176

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17 或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17 如無特殊說明，本算法用**C++**實(shí)現(xiàn)。

柚子快報(bào)邀請(qǐng)碼778899分享：算法 C++前后綴分解

http://yzkb.51969.com/

好文鏈接