文字列 S が与えられたとします。
S1 を接頭辞として、S2 を接尾辞として含む、S の個別の部分文字列の数を見つける必要があります。
S、S1、および S2 の範囲は非常に大きく、つまり O(10^5) になる場合があります。
たとえば。
S が「abcdcd」、S1 が「ab」、S2 が「cd」であるとします。
"ababcdcd" の個別の部分文字列は、"a"、"b"、"c"、"d"、"ab"、"bc"、"cd"、"dc"、"abc"、"bcd"、" cdc」、「dcd」、「abcd」、「bcdc」、「cdcd」、「abcdc」、「bcdcd」、「abcdcd」。個別の部分文字列の総数は、Suffix Array を使用して簡単に見つけることができます。質問を解決するために同じアイデアを拡張しようとしています。
これらの部分文字列のうち、接頭辞として「ab」、接尾辞として「cd」を含む部分文字列は、「abcd」、「abcdcd」です。
したがって、答えは 2 です。
PS: Suffix Array を使用していると思いますが、その方法はわかりません。助けてください。