サブタスクの既知の複雑さを伴うアルゴリズムの複雑さ

Question

動的プログラミングアルゴリズムの入力は、単一のn長のシーケンスです。このアルゴリズムは、シーケンスの可能なすべての部分文字列を考慮し、kの長い部分文字列については、O（k）時間の値を計算する。

このアルゴリズムの実行時間を見積もる方法を教えてもらえませんか？

Answer 1

[OK]を、ので掘るみましょう。

7  abcdefg 
6  abcdef 
6  bcdefg 
5  abcde 
5  bcdef 
5  cdefg 
. 
. 
. 

OK、長さnの文字列のために、我々は長さn-1の2ストリング、長さn-2の3、...、長さ1のnを持っているので。