本文介绍了计算不同的非空字符串,它们是所有四个字符串的子序列的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

这是一个 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.

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

09-25 11:43