计算不同的非空字符串，它们是所有四个字符串的子序列 [英] count distinct non-empty strings which are subsequences of all four strings

问题描述

这是一个 spoj问题，要求您计算不同的非空字符串，全部四个弦的子序列.例如

Here is a spoj problem which asks you to count distinct non-empty strings which are subsequences of all four strings . For Example

Input:
 aabb
 abab
 baba
 acba

Output:
 4
The four sequences are "a", "b", "aa", and "ab".

我该如何解决这个问题?

How can I solve this problem ?

推荐答案

为了不破坏乐趣，我没有提供完整的答案，只是给您一些想法.

In order not to ruin the fun, I do not post a complete answer, but just give you some idea.

将四个字符串写为 A ， B ， C ， D .

Write the four strings as A, B, C, D.

对于非负整数 i ，为 A 的子字符串写 A< i> ，该子字符串是通过删除第一个我字母.相同的符号适用于 B< i> ， C< i> ， D< i> .

For a non-negative integer i, write A<i> for the substring of A obtained by removing the first i letters. The same notation applies to B<i>, C<i>, D<i>.

对于字母 X (从 a 到 z )和四个非负整数 i ， j ， k ， l ，将 F(X，i，j，k，l)定义为数字 A< i> ， B< j> ， C< C< C> ， D< l> 以字母 X 开头.

For a letter X (from a to z) and four non-negative integers i, j, k, l, define F(X, i, j, k, l) to be the number of different common subsequences of A<i>, B<j>, C<k>, D<l> which start with the letter X.

尝试查找这些 F 之间的重复关系.这提供了一种动态编程方法.

Try to find a recurrence relation between these F. This gives a dynamic programming approach.

此处有更多详细信息.

F(X，i，j，k，l)的计算公式如下:设 i0 为 i 之后的第一个索引这样 A [i0] = X .让 j0 ， k0 ， l0 相似地定义.

F(X, i, j, k, l) can be calculated as follows: let i0 be the first index after i such that A[i0] = X. Let j0, k0, l0 be similarly defined.

仅当 X 出现在所有四个子字符串中.否则，很明显 F(X，i，j，k，l)= 0 .

The indice i0, j0, k0, l0 will be defined only if X occurs in all four substrings. Otherwise, it is clear that F(X, i, j, k, l) = 0.

一旦全部定义了四个索引， A< i> ， B< j> ， C< C< C> 的任何常见子序列，以 X 开头的 D< l> 的格式为 X s ，其中 s 是常见的子序列 A< i0> ， B< j0> ， C< l0> ， D< l0> .因此公式为:

Once the four indice are all defined, any common subsequence of A<i>, B<j>, C<k>, D<l> starting with X will be of the form X s, where s is a common subsequence of A<i0>, B<j0>, C<k0>, D<l0>. Hence the formula:

F(X，i，j，k，l)=所有F(Y，i0，j0，k0，l0)的总和，

总和在从 a 到 z 的所有 Y 上进行.

where the sum runs over all Y from a to z.

最后一招:使用延迟传播来避免无用的计算.

Last trick: use lazy propagation to avoid useless calculations.

这篇关于计算不同的非空字符串，它们是所有四个字符串的子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！