Counting Distinct Common Subsequences in Three Strings

Given three character sequences S₁, S₂, and S₃, count the number of distinct common subsequences that appear in all three sequences, excluding the empty subsequence.

A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

Hint: You may use a 3-dimensional dynamic programming approach. For indices i, j, k (1-indexed) and dp[i][j][k] representing the count of distinct common subsequences in the prefixes S₁[1..i], S₂[1..j], S₃[1..k] (excluding the empty subsequence), the recurrences are as follows:

\(\displaystyle dp[i][j][k]=\begin{cases}dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1] \; - \; dp[i-1][j-1][k]-dp[i-1][j][k-1]-dp[i][j-1][k-1]+dp[i-1][j-1][k-1]+1,&\\ \text{if }S_{1}[i]=S_{2}[j]=S_{3}[k],\\ dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1] \; - \; dp[i-1][j-1][k]-dp[i-1][j][k-1]-dp[i][j-1][k-1]+dp[i-1][j-1][k-1],&\\ \text{otherwise.}\end{cases}\)

inputFormat

The input consists of three lines. Each line contains a non-empty string representing a sequence of characters.

outputFormat

Output a single integer representing the number of distinct common subsequences (non-empty) shared by the three sequences.

sample

a
a
a

1