1樓：時間拓荒者
在PAM上dp就好了，類似CF906E，複雜度是線性帶乙個字符集大小的。（貌似用manacher可以線性，不會/kk）
大概就是這樣的：（分析可以見回文樹 - OI Wiki）
f[0]=0,g[0]=1;
for(int i=1;i<=slen;i++){
last=insert(last,s[i],i);
for(int pos=last;pos>1;pos=slink[pos]){
g[pos]=i-(len[slink[pos]]+dif[pos]);
if(dif[fail[pos]]==dif[pos]&&f[g[pos]]>f[g[fail[pos]]])
g[pos]=g[fail[pos]];
if(i%2==0){
if(f[i]>f[g[pos]]+1)
f[i]=f[g[pos]]+1,pre[i]=g[pos];
if(s[i]==s[i-1]&&f[i-2]
2樓：將勸酒
動態規劃，f[i]表示前 i最少包涵幾個回文串。if(s[j-1] == s[i-1]), f[i]可以更新為f[j]+1.
輸出結果為f[s.size] - 1.
3樓：Joker
先來乙個 N^2 的演算法：
字串 Hash 預處理，並對反轉的串進行 Hash 預處理，於是可以得到任何乙個字串的 Hash 值和字串倒序的 Hash 值。這裡用值域大一些的 Hash 即可，不需要雜湊表，只取 Hash 函式，做到衝撞概率低於機器斷電概率即可，大約是 6 個 uint32 就夠了。用對大質數取模的 Hash 避免簡單的構造衝撞的方法。
於是你可以 O(1) 判斷字串是不是回文串。
之後 (左閉右開區間)
if (valid(0, i)==true) DP[i] = 0;
else DP[i] = min( DP[j] + 1 where (valid(j, i) == true) );
再來乙個確定性的做法：
預處理用字尾陣列，可以做到 O(logN) 判斷字串是不是回文串，總的複雜度為 O(N^2*logN)。
求教乙個字串生成的演算法？
我覺得沒必要考慮高不高效，只要考慮好生成的字串怎麼存就行了，因為你要的是長度為n的所有組合，那麼必然會輸出所有的字串，所以不管啥演算法都不能使時間複雜度降低到輸出所用時間以下。 zanxas 乙個string佔多少記憶體？用char陣列還是string考慮過沒？26 10 36 36的五次方是多少？...
python如何判斷乙個字串是浮點型資料？
defis number text try float text if in text return 0 浮點 else return 1 整數 except pass return 1 不是數字 學而時習 defget float s if not ins return None try retu...
在C語言中，怎麼做到輸入乙個字串,過濾此串,只保留串中的數字,並進行加減乘除？
class Catbool IsBreak charCh return false intStrToInt char Str int Sum 0 for p p return Sig Sum public void InputStr char Str int Size char p Str 1 ch...