24

長さ n の文字列の場合、すべての部分文字列を計算する式は次のとおりです。 n(n+1)/2 この式を直感的に理解するのに誰か助けてくれませんか?

ウィキペディアは次 のように述べています。 「記号が一度だけ出現する長さの文字列の部分文字列の数は、部分文字列を開始/終了する記号間の2つの異なる場所を選択する方法の数です」

4

6 に答える 6

64

これを理解するには、部分文字列には開始インデックスと終了インデックスの 2 つのパラメーターが必要であることに注意してください。

例: string str = "Hello World"; // 長さ == 11

H、e、l、l、o、W、o、r、l、d. He、el、ll、lo、o、W、Wo、または rl、ld の 2 文字を一度に取得します。次に、3文字を取ることによって: Hel, .. など.

したがって、部分文字列の総数は 11 + 10 + 9 + .. + 1 であり、一般にfor i from 1 to n、n - i + 1部分文字列があります。サミットによって：

i = 1 から n までのシグマ (n + 1 - i)n * (n + 1) - n * (n + 1) / 2は、n * (n + 1) / 2

于 2012-09-14T05:32:43.667 に答える
8

部分文字列は、元の文字列の開始位置と終了位置によって決まります。任意の部分文字列について、これら 2 つの終点があります。逆に、文字列内の任意の 2 文字には、それらのポイントで開始および終了する部分文字列が 1 つだけ存在します。

したがって、すべての部分文字列の数は、(別個である必要はない) 文字のすべてのペアの数です。

n*(n-1)/2異なる文字のペアがあります。また、n である不明確なペアを追加する必要があります。

したがって、総数はn * (n-1) / 2 + n = n * (n+1) / 2です。

于 2012-09-14T05:30:02.350 に答える
6

これは、長さ 1 (正確には n) のすべての部分文字列、長さ 2 (n-1) のすべての部分文字列、および長さ n (適切な文字列) のすべての部分文字列の合計です。次に、n + n-1 + n-2 ... + 1 = (n * (n+1)) / 2 になります。

合計は自然帰納法を使用して計算でき、ガウスが学校でこの合計を解いたことからも知られています。

于 2012-09-14T05:30:30.577 に答える
1

私は数学が得意ではありませんがsubstrings、文字列とは何か、文字列を取得する可能性は何であるかsubstringsを説明しようと思います。

例を見てみましょう。「MOBILE」これは6文字の文字列であり、式n（n + 1）/ 2によると、結果は6（6 + 1）/ 2=21になります。

したがって、部分文字列は、文字列全体の間に開始インデックスと終了インデックスを持つ任意の文字列です。

文字列「MOBILE」では、次の部分文字列を使用できます。

ステップ1：「M」開始インデックス「M」および終了インデックス「M」これは1つの可能性です

ステップ2：「MO」開始インデックス「M」および終了インデックス「O」これは2番目の可能性です

。

。

ステップ5：「MOBIL」開始インデックス「M」および終了インデックス「L」これは5番目の可能性です

。

。

ステップ8：「OB」開始インデックス「O」および終了インデックス「B」これは8つの可能性です

。

。

ステップ21：「MOBILE」開始インデックス「E」と終了インデックス「E」これは21番目の可能性です

これらは、文字列内にサブ文字列を含める可能性であり、サブ文字列内の終了インデックスは開始インデックスより小さくすることはできません。

于 2012-09-14T05:36:11.993 に答える