我需要證明在一個包含多個字符 n 的字串中，最多有 n 個不同的、非空的回文子串是可能的。我可以理解這是因為每個字符本身都可以是回文，因此可能的最大子串數將等于字串中的字符數。但是，我似乎無法以數學證明的形式表達這一點。我該怎么做？
uj5u.com熱心網友回復：
給定xc，其中x是任何字串，c是任何字符：
所有子XC已經不在X必須為后綴的XC。如果他們是回文，那么他們有形式CYC，其中CY是后綴X和?是回文或空。
想象一下，有兩個這樣的新回文后綴。由于它們是同一字串的不同后綴，因此它們的長度必須不同，因此我們有cyczc，其中z和ycz都是回文或空。
如果ycz是回文，則需要考慮幾種情況。
如果 len(y) = len(z)，那么這意味著y = z并且czc因此已經是x的子串——這是矛盾的。
如果z更短，那么我們可以再次劃分為cz r cwczc，但是z是回文所以z r = z并且我們有相同的矛盾。
如果?是更長的時間，那么我們可以劃分為cycwcy [R ?，具有世界競爭力年鑒[R = Z，這是一個回文，所以也Z = YCW，再次使矛盾CZC已經出現在X。
所以......向字串添加單個字符最多可以引入一個新的回文子字串。因此，任何字串中此類子字串的總數不能超過字串的長度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/387552.html