単純な数え方として、 \(R\) と \(D\) の長さだけ辻褄が合うように決めて、あとは長さ \(|R|\) の文字列と長さ \(|D|\) の文字列をすべて数える、という方法が考えられます。しかしこのままでは「 aabaa 」のような文字列が \((D,R)=\) (a,aba) と (aa,b) で重複して数えられてしまいます。このような重複を避けて数え上げる必要があります。

\(R\) が空文字列になることを許して考える

\(R\) を空文字列とすることを許したものを「広義DRD文字列」と呼び、広義DRD文字列でない文字列を非-広義DRD文字列と呼ぶことにします。すると、

• \(S\) が広義DRD文字列である ⇔ \(S\) の（自身を除く）ある接頭辞と接尾辞が一致する

となります。⇒は明らかです。⇐は、接頭辞と接尾辞が重複しない場合は明らかです。重複する場合、その接頭辞の長さを \(N-x\) とすると \(x<N/2\) が成立します。また \(S\) 中では距離が \(x\) 文字なら同じ文字になるため、\(N=ax+b\) \((1\leq b\leq x)\)と表すと長さ \(b\) の接頭辞と接尾辞が一致し、 \(b<N/2\) より、これらは重複しないことがわかります。

以下、空文字列であっても良いかをわかりやすくするため、\(D, R\) 及びそれに装飾が付いた文字は空でない必要がある文字列、 \(P\) 及びそれに装飾が付いた文字は空であっても良い文字列として記述します。

\(S\) が広義DRD文字列、つまり \(S=D+P+D\) と表せる場合、 \(D\) が広義DRD文字列であるとすると、ある長さで接頭辞と接尾辞が一致するため、 \(D\) のある接頭辞 \(D'\) \((\neq D)\) を用いて \(S=D'+P'+D'\) とも表すことができます。さらに \(D'\) が広義DRD文字列であれば同様の操作を繰り返すことができます。これにより、任意の広義DRD文字列 \(S\) は、非-広義DRD文字列 \(D^*\) を用いて \(S=D^* + P^* + D^*\) と表すことができます。

さらに、ある広義DRD文字列 \(S\) が \(S=D_1+P_1+D_1=D_2+P_2+D_2\) と \(2\) 通りに表せたとします。すると、 \(D_1\) と \(D_2\) のどちらかが長くなり、その長い方の文字列は（自身を除く）ある接頭辞と接尾辞が共通するため、広義DRD文字列です。よって、任意の広義DRD文字列 \(S\) について、非-広義DRD文字列 \(D^*\) を用いて \(S=D^* + P^* + D^*\) と表す方法は一意です。

つまり、広義DRD文字列を数え上げる際には、「文字列 \(D\) は非-広義DRD文字列である」という制約を課した上で、 \(D, P\) の長さを先に決めて、長さ \(|P|\) の文字列と長さ \(|D|\) の文字列をすべて数える、という方針にすれば重複なく数えられることがわかります。

広義DRD文字列を数え上げ

以上の考察を元にして数え上げます。 \(P\) の文字列長を \(i\) とすると、 \(D\) として考えられるのは長さ \((N-i)/2\) の非-広義DRD文字列です。よって、長さ \(N\) の非-広義DRD文字列の総数を \(f(N)\) と定める（整数でない \(x\) に対しては \(f(x)=0\) と定める）と、長さ \(N\) の広義DRD文字列の総数は

\[ \sum_{i=0}^{N-2} M^i f\left(\frac{N-i}{2}\right) = \sum_{i=2}^N M^{N-i} f\left(\frac{i}{2}\right) =\sum_{j=1}^{\lfloor \frac{N}{2} \rfloor} M^{N-2j} f(j)\]

となります。 \(M^N\) からこの値を引けば、非-広義DRD文字列の総数 \(f(N)\) を求めることができます。よって、 \(j\) の小さい方から \(M^{-2j}f(j)\) の累積和を計算しながら \(f(j)\) を順に更新することで、 \(O(N)\) で広義DRD文字列の総数を求めることができます。

\(R\) が空文字列でないものに限定

元の意味でのDRD文字列（ \(R\) が空であってはならない）を狭義DRD文字列と呼ぶことにします。ACを得るには、これまで数えた広義DRD文字列から狭義DRD文字列ではないもの、つまり「 \(S=D+D\) と表せるが \(S=D+R+D\) とは表せないもの」を除外する必要があります。この除外すべき文字列は、 \(N\) が奇数の時は明らかに存在しませんが、 \(N\) が偶数の時は、 \(S\) の前半が後半と一致し、かつ前半が「長さ \(N/2\) の非-広義DRD文字列」になっているものが該当します。

• 【理由】 \(S=D+D\) と表せるとする。このとき、 \(D\) が広義DRD文字列である場合は、 \(D=D'+P'+D'\) と表せるので、 \(S=D'+(P'+D'+D'+P')+D'\) と表すことができ、 \(S\) は狭義DRD文字列になる。逆に、 \(S\) が狭義DRD文字列である場合は、 \(S=D''+R''+D''\) と表せるが、 \(D''\) は \(D'\) の接頭辞でありかつ接尾辞でもあるので、 \(D'\) は広義DRD文字列である。以上より、 \(S=D+D\) と表せるが \(S=D+R+D\) と表せないものは、「長さ \(N/2\) の非-広義DRD文字列」を \(2\) つ繋げた文字列のみである。

\(N\) が偶数の場合、長さ \(N/2\) の広義DRD文字列は上記の数え上げパートで既に求めてあるので、容易に除外できます。

以上により、（狭義）DRD文字列を \(O(N)\) 時間で数え上げることができました。