2016網易機試編程題中的字元串問題？

01-16

由a,b,c三個字元組成的長度為n的字元串共3^n種，包含(abc,acb,bac,bca,cab,cba)任意一個子串的字元串有多少種？
題主主要想問的是關於概率方面的解答。感覺像是高中的排列組合問題，但又做不出來。
編程的話，將abc用124分別表示，result表示結果，深度遍歷整個樹（棧來存儲狀態），碰到最後三個數加起來為7的情況下剪枝，result += 3^x（x為總層數減去當層數）。

記長度為k，不包含該集合任意子串，最後兩位相同的字元串數目為 $S_k$

記長度為k，不包含該集合任意子串，最後兩位不同的字元串數目為 $D_k$

則

$D_{k+1}=2S_k+D_k$

$S_{k+1}=S_k+D_k$

我們要求的是

$3^k-S_k-D_k$

遞推可解，時間複雜度O(n)。

進一步地，寫成矩陣形式 $egin{bmatrix} S_{k+1} \ D_{k+1} end{bmatrix} = egin{bmatrix} 1 1 \ 2 1 end{bmatrix}egin{bmatrix} S_k \ D_k end{bmatrix}$

矩陣特徵值為

$(1-lambda)^2-2=lambda^2-2lambda-1=0$

$lambda_{1,2}=1 pm sqrt{2}$

對應特徵向量

$lambda_1 = 1+sqrt{2} ext{, }v_1 = egin{bmatrix} 1 \ sqrt{2} end{bmatrix}$

$lambda_2 = 1-sqrt{2} ext{, }v_2 = egin{bmatrix} -1 \ sqrt{2} end{bmatrix}$

已知

$S_2=3 ext{, }D_2=6$

為了方便計算，我們倒算出

$S_1=3 ext{, }D_1=0$ （注意這兩個數並不具有實際意義，只是為了計算方便而已）

則

$egin{bmatrix}S_1 \ D_1 end{bmatrix} = egin{bmatrix}3 \ 0 end{bmatrix} = frac{3}{2}v_1-frac{3}{2}v_2$

$egin{bmatrix}S_k \ D_k end{bmatrix} = egin{bmatrix} 1 1 \ 2 1 end{bmatrix}^{k-1}egin{bmatrix}S_1 \ D_1 end{bmatrix} = egin{bmatrix} 1 1 \ 2 1 end{bmatrix}^{k-1}(frac{3}{2}v_1-frac{3}{2}v_2)$

$=frac{3}{2}(lambda_1^{k-1}v_1-lambda_2^{k-1}v_2)=frac{3}{2}egin{bmatrix}(1+sqrt{2})^{k-1}+(1-sqrt{2})^{k-1} \ sqrt{2}(1+sqrt{2})^{k-1}-sqrt{2}(1-sqrt{2})^{k-1}end{bmatrix}$

所以

$S_k+D_k = frac{3}{2}[(1+sqrt{2})^k+(1-sqrt{2})^k]$

注意到 $1-sqrt{2} approx 0.41421 <1$ ，因此當k充分大時，這一項可以忽略。

實際上，只需取k=4就有

$frac{3}{2}(1-sqrt{2})^4<0.05$

所以

$S_k+D_k approx frac{3}{2} (1+sqrt{2})^k$

我們要求的是包含該集合中子串的字元串，即為

$3^k-S_k-D_k approx 3^k - frac{3}{2}(1+sqrt{2})^k$

理論上來說，時間複雜度O(1)，問題是沒法用高精度，所以k算不了太大，還不如用遞推。

複雜度O(n)

主要工作是找出DP的狀態轉移方程。

import sys max = 31 if __name__ == "__main__": n = int(sys.stdin.readline().strip()) t1 = [0, 0, 0] # 後兩位一樣為真 t2 = [0, 0, 0] # 後兩位不一樣為真 t3 = [0, 0, 3] # 後兩位一樣為假 t4 = [0, 3, 6] # 後兩位不一樣為假 for i in range(3, max): x1, x2, x3, x4 = t1[-1], t2[-1], t3[-1], t4[-1] t1.append(x1 + x2) t2.append(2 * x1 + 2 * x2 + x4) t3.append(x3 + x4) t4.append(2 * x3 + x4) ans = [t3[i] + t4[i] for i in range(max)] print(ans[n])

備忘錄式DP，簡單暴力比對了下結果，應該沒啥問題，當然細節性能有待改進，但是算到n=990也是瞬間出結果（因為python遞歸到1000層就異常了）

import sys n = int(sys.argv[1]) mem = {} def f(s): if len(set(s[-3 :])) == 3: return 0 if len(s) == n: return 1 last = s[-2 :] key = len(s), last if key in mem: return mem[key] mem[key] = r = sum([f(s + c) for c in "abc"]) return r print 3 ** n - f("")

Richard的方法，到矩陣那一步，然後算個快速冪，logn級別時間得到精確解。

不過如果用C/Cpp你還得寫個高精度計算……

設 $a_i$ 表示長度為 $i$ ，不包含6個目標串，且結尾兩個字元相同的字元串數量；

設 $b_i$ 表示長度為 $i$ ，不包含6個目標串，且結尾兩個字元不同的字元串數量；

設 $c_i$ 表示長度為 $i$ ，包含目標串的字元串數量。

初始化： $a_1 = 0, a_2 = 3; b_1 = 0, b_2 = 6, c_1 = 0, c_2 = 0$

當 $n >= 3$ 時, 得到如下遞推公式

$a_i = a_{i-1} + b_{i - 1}$ ;

$b_i = 2a_{i-1} + b_{i-1}$ ;

$c_i = 3c_{i-1} + b_{i-1}$ ;

對這道題來講n大概20左右吧，畢竟種類的總數是 $3^n$ ，所以這樣所應該就OK了,複雜度O(n)。

如果（拋開這道題）n可以取很大，比如 $10^8$ 這種數量級，遞推關係不變，可以考慮矩陣加速的做法：

$left{ {egin{array}{*{20}c} c_i \ a_i \ b_i \ end{array}} ight} =left{ {egin{array}{*{20}c} 3 0 1 \ 0 1 1 \ 0 2 1 end{array}} ight} left{ {egin{array}{*{20}c} c_{i-1} \ a_{i-1} \ b_{i-1} \ end{array}} ight}$

複雜度O(log n)

純數學方法，這題可以求出通項公式的

後一位可能的情況與前兩位有關，前兩位相同則這一位有三種情況，前兩位不同則這一位有兩種情況，這樣就可以得出後面的通項公式，不知道題主怎麼看

提供一個相對易懂的思路。

求包含的字元串數量，等價於求總數減去不包含的數量（題目好像也這樣提示了）。由於給出的字元串長度只有3位，可以手工構造一下所有的狀態。一個長度為n的字元串可以由前n-1個字元加上第n個字元組成。設一個長度為2的字元串，它的第一位表示某字元串的第n-1個字元，第二位表示某字元串的第n位字元，將它枚舉出來得：aa、bb、cc、ab、ac、ba、bc、ca、cb。

根據題目構造轉移矩陣（1表示可以拼接在一起，反之亦然。aa和ac可以拼接成aac，但ab和ca不能拼接在一起，根據題目ab和bc拼接成的abc也不行）

這相當於求一個有向圖中問從某個點走k步到某個點的方法數，根據上面的矩陣進行矩陣連乘或矩陣快速冪得到Mat^(n-2)（因為長度是從2開始的）， $sum_{i=1,j=1}^{n=9}{Mat[i][j]}$ 即為所求的方法數ans。所以最後答案為3^n - ans。

（原諒我渣渣的文筆......）

看了一遍問題覺得這是一個概率題，刷了回答回來再看問題還是概率題。是我沒看懂么？

題目看了兩遍沒看懂的覺得更羞恥，悲傷

好像leetcode46題

就是求某個字元串中是否包含連續不同的三個字元。

這個題目我只有80%的通過率，沒明白是什麼原因！我是按上面的遞推公式計算的