子串和子序列

-2

在一個長度爲n的字符串中，我可以擁有多少個子串和子序列...即使通過從s中刪除任何前綴和任何後綴來獲得子串，序列是通過刪除零個或多個不需要s的連續位置而形成的任何字符串。子串和子序列

哪種語言？ –

我正在學習編譯器，所以我只需要它的一般正式形式... – user3419748

這個問題似乎是題外話題，因爲它是關於數學。 – hivert

假設你沒有忽略重複：

子串= N（N + 1）/ 2

計數的1米長度的子串的數目= N
計數2長度的數子串= n-1個
計數的3個長度的子字符串= n-2個
....數
計數n長度的子串= n的數 - 第（n-1）= 1

概括爲從1到n的數字序列的總和。

子序列= 2^N

字符串作爲一個位陣列的思考。要麼在你的子序列中包含字符要麼不要。有2^n個組合。

2014-03-26 13:16:57

作爲一個子字符串，一個長度爲1的字符串只有一個子字符串，而長度爲2的有3個，長度爲3的有6個，有4個有10個，有5個有15個，有6個有21個。我可以找到它們之間沒有關係.. – user3419748

@ user3419748我編輯了我的答案，包括一個解釋。 –

是否爲「空」被視爲有效序列？ – user3419748

回答