問題 8 : 一致する接頭辞と接尾辞 5 Rust(Beta)編（paizaランク S 相当）

英小文字からなる長さ N の文字列 S が入力として与えられるので、1 ≦ i ≦ N を満たす i それぞれについて、以下の問題に答えてください。
・S の 1 文字目から i 文字目までの部分文字列を T_{i} とする。T_{i} の接頭辞であり、接尾辞でもあるような文字列のうち最長のものの長さを出力してください。
ただし、空文字列の長さは 0 とし、
文字列 T の接頭辞、接尾辞は空文字列を含み、T 自身を含まないものとします。


例えば S = aabaaab に対して i = 5 の場合、
S の 1 文字目から i 文字目までの部分文字列は aabaa なので、
・接頭辞 : { φ, a, aa, aab, aaba }
・接尾辞 : { φ, a, aa, baa, abaa }
となります。接頭辞かつ接尾辞である文字列は φ, a, aa の 3 つなので、答えは aa の長さである 2 となります。

ヒント :
以下にアルゴリズムの方針を軽く示すので、参考にしてください。
i 文字目までの部分文字列に対する答えを dp_i とします。

i 文字目までの部分文字列が一致するためには、画像の赤い部分が一致する必要があることに注意すると、何かが見えてくるかもしれません。