2 zss19910423 zss19910423 于 2015.07.08 20:28 提问

A序列关于 B序列的多个最长子串

如果有序列为
A=[01111000110];
B=[10010100110];

定义A/B=[011,110,00110]; 寻找A中的最长前缀且该前缀也存在于B中。

这个用matlab怎么写啊?或者可以提供思路吗?

4个回答

caozhy
caozhy   Ds   Rxr 2015.07.08 21:26
已采纳

C/C++可以用动态规划,思路是,首先将A和B连接在一起,然后产生一个后缀数组
然后对后缀数组排序
然后比较相邻的两个,有多少相同的。
最后得到相同长度最大的。

zss19910423
zss19910423 我看懂了点点,但是不知道怎么实现
2 年多之前 回复
caozhy
caozhy   Ds   Rxr 2015.07.08 21:32

举个例子,比如比较
00101101
10100100
我们首先连接它们
00101101#10100100
然后得到一个如下的数组:

00101101#10100100
0101101#10100100
101101#10100100
01101#10100100
...
00
0
然后对上面的这个后缀数组排序
(这里省略)
...
101101#10100100
10100100
101#10100100
...
很明显这三项排在一起。因为我们比较的是两个数据,所以,有#的必须和没有#的比。
这里
101101#10100100
10100100
前三个相同
或者
10100100
101#10100100
前三个相同。

比较别的相邻的项,没有超过3个的。
所以结果就是101

zss19910423
zss19910423 a=00101101; b=10100100; 大侠,你好,我是想要得到这样的序列c=a/b=0010,1,101
2 年多之前 回复
zss19910423
zss19910423   2015.07.09 08:34

a=00101101;
b=10100100;

大侠,你好,我是想要得到这样的序列c=a/b=0010,1,101

caozhy
caozhy 那就把所有匹配的都输出。算法一样。
2 年多之前 回复
ouyangyong_kang
ouyangyong_kang   2015.08.21 22:29

使用正则表达式呀,哥们。这个思路。

Csdn user default icon
上传中...
上传图片
插入图片