找回密码
 加入
搜索
AUTOIT CN»论坛 › AU3交流 › 『 提问交流 』 › 题目：给定一组字符串，要求求出一个最短的字符串：使得 ...
12下一页
返回列表 发新帖
查看: 8011|回复: 16

[效率算法] 题目：给定一组字符串，要求求出一个最短的字符串：使得它包含所有给出的字符串

 火.. [复制链接]
happytc
发表于 2011-12-7 23:52:40 | 显示全部楼层 |阅读模式
例如：比如"a","bc","ca"，那么应该得到字符串是"bca"

为了让大家明白，再举一个例子：
"cabe", "bef", "abex"----->这三个字串中,输出结果应该是:cabexbef.
                                <注意了,是最短的字串>
                                 输入字符仅限ASCII码

看看那个的算法最好！
字符串, 最好

评分

参与人数 1金钱 +30 收起 理由
afan + 30

查看全部评分

相关帖子
回复

举报

Au3代码高亮发贴标签： [AU3] 你的代码 [/AU3]                   支持论坛的发展，请添加此》》网址导航《《为您的主页          
afan
发表于 2011-12-8 01:31:19 | 显示全部楼层
字符数应该可以确定，不过位置似乎有多样性~ 比如第二个例子 befcabex 应该也符合条件…
回复

举报

happytc
 楼主| 发表于 2011-12-8 02:48:04 | 显示全部楼层
回复 2# afan

很有意思的问题，为了让大家容易理解，我是把原问题简化说明了下。
大家做做，对训练思维很有帮助的。

我发现本论坛问的问题基本都是‘如何点某个按纽’之类的最初级的问题，很少讨论算法之类的问题


原题目：
===============================================
Name: Shortest Common Superstring [SR9] 3

Input: A finite set R={r1,r2,...,rm} of binary strings (sequences of 0 and 1); positive integer k.

Question: Is there a binary string w of length at most k such that every string in R is a substring of w, i.e. for each r in R, w can be decomposed as w=w0rw1 where w0, w1 are (possibly empty) binary strings?

===============================================
回复

举报

happytc
 楼主| 发表于 2011-12-8 03:03:38 | 显示全部楼层
字符数应该可以确定，不过位置似乎有多样性~ 比如第二个例子 befcabex 应该也符合条件…
afan 发表于 2011-12-8 01:31


的确可能有好几种可能性的答案。

我的思路是：
设字串a是组合x0,x1.....xn的最短公共串
则x0,x1....xn+1的最短公共串是：
若a包含xn+1,返回a
若a不包含xn+1
  若a的前m个字符与xn+1的后m个字符相等.....
  若a的后m个字符与xn+1的前m个字符相等.....

这个麻烦的在于a可能有好几种可能性

这就得2^n的DP了
回复

举报

afan
发表于 2011-12-8 03:09:46 | 显示全部楼层
我的想法是先按字符串的长度从长到短排序
然后分别从字符串中循环截取一定数量包含头部或包含尾部的字符串进行声明
在之后的字符串中如果整体已声明过则该字符串可以删除
余下的字符串进行收尾相连……

我开始想晕了…… 现在想睡了 zzZ
回复

举报

3mile
发表于 2011-12-8 11:04:12 | 显示全部楼层
好玩的东东又来了，试下，也许有缺陷。
#include <array.au3>
Global $out

Local $str[3] = ["cabe", "bef", "abex"]
$fin=simplified($str)
$t=_ArrayToString($fin,"")
MsgBox(0,0,$t)

Func simplified($str)
        Local $flag_array[1], $flag
        For $i = 0 To UBound($str) - 2
                For $n = $i + 1 To UBound($str) - 1
                        $flag = StringRegExp($str[$i] & $str[$n], '(\w+)(?=[^\1]*\1)', 3)
                        If UBound($flag) > 0 Then
                                ReDim $flag_array[UBound($flag_array) + 1]
                                $flag_array[UBound($flag_array) - 1] = $flag[0]
                        EndIf
                Next
        Next

        _ArrayDelete($flag_array, 0)
        $new = _ArrayUnique($flag_array)
        _ArraySort($new)
;~         _ArrayDisplay($str)
;~         _ArrayDisplay($flag_array)
        
        For $i = 1 To 1
                $len = StringLen($new[$i])
                For $n = 0 To UBound($str) - 1
                        For $k = $n + 1 To UBound($str) - 1
                                If StringInStr($str[$n], $new[$i], 1) And StringInStr($str[$k], $new[$i], 1) Then
                                        $out &= $new[$i] & " ==> " & $str[$n] & " VS " & $str[$k] & @CRLF
                                        If (StringRegExp($str[$n], '\b' & $new[$i] & '\w+\b', 0) Or StringRegExp($str[$n], '\b\w+' & $new[$i] & '\b', 0)) And _
                                                        (StringRegExp($str[$k], '\b' & $new[$i] & '\w+\b', 0) Or StringRegExp($str[$k], '\b\w+' & $new[$i] & '\b', 0)) Then
                                                $temp = StringRegExp($str[$n] & @CRLF & $str[$k], '\b' & $new[$i] & '\w+\b', 1)
                                                If Not @error Then        $left = $temp[0]
                                                
                                                $temp = StringRegExp($str[$n] & @CRLF & $str[$k], '\b\w+' & $new[$i] & '\b', 1)
                                                If Not @error Then        $right = $temp[0]                                                
                                                
;~                                                 MsgBox(0, 0, "$left=" & $left & @CRLF & "$right=" & $right)
                                                $out &= $new[$i] & " ==> " & $str[$n] & " VS " & $str[$k] & @CRLF & $right & StringReplace($left, $new[$i], "") & @CRLF
                                                $str[$n] = $right & StringReplace($left, $new[$i], "")
                                                _ArrayDelete($str, $k)
                                                simplified($str)
                                        EndIf                                        
                                EndIf
                        Next
                Next
        Next
Return $str
EndFunc   ;==>simplified

评分

参与人数 1金钱 +30 收起 理由
afan + 30

查看全部评分

回复

举报

3mile
发表于 2011-12-8 14:27:23 | 显示全部楼层
本帖最后由 3mile 于 2011-12-8 14:47 编辑

貌似还有问题，再来：
#include <array.au3>
Global $out

Local $str[4] = ["abcde", "abcd", "abc","abs"]
;~ Local $str[3] = ["bc", "ca", "a"]
;~ Local $str[6] = ["cabe", "bef", "abex","ca","be","efx"]
$fin = simplified($str)
_ArrayDisplay($fin)
$t = _ArrayToString($fin, "")
MsgBox(0, 0, $t)

Func simplified($array)
        Local $flag_array[1], $flag
        For $i = 0 To UBound($array) - 2
                For $n = $i + 1 To UBound($array) - 1
                        $flag = StringRegExp($array[$i] & $array[$n], '(\w+)(?=[^\1]*\1)', 3)
                        If UBound($flag) > 0 Then
                                ReDim $flag_array[UBound($flag_array) + 1]
                                $flag_array[UBound($flag_array) - 1] = $flag[0]
                        EndIf
                Next
        Next

        _ArrayDelete($flag_array, 0)
        $new = _ArrayUnique($flag_array)
        Local $long, $long_len = 0
        
        For $i = 1 To UBound($new) - 1
                If StringLen($new[$i]) > $long_len Then
                        $long = $new[$i]
                        $long_len = StringLen($long)
                EndIf
        Next
;~         _ArraySort($new)
;~         _ArrayDisplay($array)
;~         _ArrayDisplay($array)
;~         _ArrayDisplay($flag_array)
        
        For $n = 0 To UBound($array) - 2
                For $k = $n + 1 To UBound($array) - 1
                        Local $right = "", $left = ""
                        If $k > UBound($array) - 1 Then ContinueLoop
;~
                        If StringInStr($array[$n], $array[$k]) Then ;Or StringInStr($array[$k],$array[$n]) Then
                                _ArrayDelete($array, $k)
                                        Return simplified($array)
                        ElseIf StringInStr($array[$k], $array[$n]) Then
                                _ArrayDelete($array, $n)
                                        Return simplified($array)
                                Else
;~                                         _ArrayDisplay($array,$long)
                                If (StringRegExp($array[$n], '\b' & $long & '\w+\b', 0) Or StringRegExp($array[$n], '\b\w+' & $long & '\b', 0)) And _
                                                (StringRegExp($array[$k], '\b' & $long & '\w+\b', 0) Or StringRegExp($array[$k], '\b\w+' & $long & '\b', 0)) Then
;~                                         $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b' & $long & '\w+\b', 1)
;~                                         If Not @error Then $left = $temp[0]
;~                                         
;~                                         $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b\w+' & $long & '\b', 1)
;~                                         If Not @error Then $right = $temp[0]
;~                                         
;~                                         $array[$n] = $right & StringReplace($left, $long, "")
                                        $temp0 = StringRegExpReplace($array[$n] & $array[$k], '(\w+)\1', '\1')
                                        $temp1 = StringRegExpReplace($array[$k] & $array[$n], '(\w+)\1', '\1')
                                        If StringLen($temp0)<StringLen($temp1) Then
                                                $array[$n] =$temp0
                                                _ArrayDelete($array, $k)
                                                Return simplified($array)
                                        Else
                                                $array[$n] =$temp0
                                                _ArrayDelete($array, $k)
                                                Return simplified($array)
                                        EndIf
                                EndIf
                        EndIf
                Next
        Next
        Return $array
EndFunc   ;==>simplified

评分

参与人数 1金钱 +30 收起 理由
afan + 30

查看全部评分

回复

举报

afan
发表于 2011-12-8 16:04:15 | 显示全部楼层
貌似还有问题，再来：
3mile 发表于 2011-12-8 14:27



    似乎有点问题哦，试试
$str[3] = ['abc', 'bcde', 'gga']
回复

举报

afan
发表于 2011-12-8 16:15:59 | 显示全部楼层
本帖最后由 afan 于 2011-12-8 21:04 编辑

以下为我的题解，还可以得到所有符合条件的组合：
游客，如果您要查看本帖隐藏内容请回复

评分

参与人数 1金钱 +35 贡献 +5 收起 理由
3mile + 35 + 5 学习了

查看全部评分

回复

举报

3mile
发表于 2011-12-8 16:35:21 | 显示全部楼层
再来
#include <array.au3>
Global $out

;~ Local $str[4] = ["abcde", "abcd", "abc","abs"]
;~ Local $str[3] = ["bc", "ca", "a"]
;~ Local $str[6] = ["cabe", "bef", "abex","ca","be","efx"]
Local $str[3] = ['abc', 'bcde', 'gga']
$fin = simplified($str)
_ArrayDisplay($fin)
$t = _ArrayToString($fin, "")
MsgBox(0, 0, $t)

Func simplified($array)
        Local $flag_array[1], $flag
        For $i = 0 To UBound($array) - 2
                For $n = $i + 1 To UBound($array) - 1
                        $flag = StringRegExp($array[$i] & $array[$n], '(\w+)(?=[^\1]*\1)', 3)
                        If UBound($flag) > 0 Then
                                ReDim $flag_array[UBound($flag_array) + 1]
                                $flag_array[UBound($flag_array) - 1] = $flag[0]
                        EndIf
                Next
        Next

        _ArrayDelete($flag_array, 0)
        $new = _ArrayUnique($flag_array)
        Local $long, $long_len = 0
        
        For $i = 1 To UBound($new) - 1
                If StringLen($new[$i]) > $long_len Then
                        $long = $new[$i]
                        $long_len = StringLen($long)
                EndIf
        Next
;~         _ArraySort($new)
;~         _ArrayDisplay($array)
;~         _ArrayDisplay($array)
;~         _ArrayDisplay($flag_array)
        
        For $n = 0 To UBound($array) - 2
                For $k = $n + 1 To UBound($array) - 1
                        Local $right = "", $left = ""
                        If $k > UBound($array) - 1 Then ContinueLoop
;~
                        If StringInStr($array[$n], $array[$k]) Then ;Or StringInStr($array[$k],$array[$n]) Then
                                _ArrayDelete($array, $k)
                                        Return simplified($array)
                        ElseIf StringInStr($array[$k], $array[$n]) Then
                                _ArrayDelete($array, $n)
                                        Return simplified($array)
                                Else
;~                                         _ArrayDisplay($array,$long)
                                If (StringRegExp($array[$n], '\b' & $long & '\w+\b', 0) Or StringRegExp($array[$n], '\b\w+' & $long & '\b', 0)) And _
                                                (StringRegExp($array[$k], '\b' & $long & '\w+\b', 0) Or StringRegExp($array[$k], '\b\w+' & $long & '\b', 0)) Then
;~                                         $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b' & $long & '\w+\b', 1)
;~                                         If Not @error Then $left = $temp[0]
;~                                         
;~                                         $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b\w+' & $long & '\b', 1)
;~                                         If Not @error Then $right = $temp[0]
;~                                         
;~                                         $array[$n] = $right & StringReplace($left, $long, "")
                                        $temp0 = StringRegExpReplace($array[$n] & $array[$k], '(?<!'&$array[$n]&')(\w+)\1', '\1')
                                        $temp1 = StringRegExpReplace($array[$k] & $array[$n], '(?<!'&$array[$k]&')(\w+)\1', '\1')
                                        If StringLen($temp0)<StringLen($temp1) Then
                                                $array[$n] =$temp0
                                                _ArrayDelete($array, $k)
                                                Return simplified($array)
                                        Else
                                                $array[$n] =$temp0
                                                _ArrayDelete($array, $k)
                                                Return simplified($array)
                                        EndIf
                                EndIf
                        EndIf
                Next
        Next
        Return $array
EndFunc   ;==>simplified
回复

举报

afan
发表于 2011-12-8 16:48:58 | 显示全部楼层
回复 10# 3mile


    貌似还是有点问题，用9#的字符串测试，得到的输出为 abcdegga ，正确的应该是 ggabcde
回复

举报

3mile
发表于 2011-12-8 17:13:01 | 显示全部楼层
回复 11# afan
最后试下：
#include <array.au3>
Global $out
Local $ts = TimerInit()
;~ Local $str[4] = ["abcde", "abcd", "abc","abs"]
;~ Local $str[3] = ["bc", "ca", "a"]
Local $str[6] = ["cabe", "bef", "abex","ca","be","efx"]
;~ Local $str[3] = ['gga', 'bcde', 'abc']
        _ArraySort($str)        
        
$fin = simplified($str)
;~ _ArrayDisplay($fin)
$t = _ArrayToString($fin, "")
MsgBox(0, TimerDiff($ts), $t)

Func simplified($array)
        Local $flag_array[1], $flag
        For $i = 0 To UBound($array) - 2
                For $n = $i + 1 To UBound($array) - 1
                        $flag = StringRegExp($array[$i] & $array[$n], '(\w+)(?=[^\1]*\1)', 3)
                        If UBound($flag) > 0 Then
                                ReDim $flag_array[UBound($flag_array) + 1]
                                $flag_array[UBound($flag_array) - 1] = $flag[0]
                        EndIf
                Next
        Next

        _ArrayDelete($flag_array, 0)
        $new = _ArrayUnique($flag_array)
        Local $long, $long_len = 0
        
        For $i = 1 To UBound($new) - 1
                If StringLen($new[$i]) > $long_len Then
                        $long = $new[$i]
                        $long_len = StringLen($long)
                EndIf
        Next
;~         _ArraySort($new)
;~         _ArrayDisplay($array)
;~         _ArrayDisplay($array)
;~         _ArrayDisplay($flag_array)
        
        For $n = 0 To UBound($array) - 2
                For $k = $n + 1 To UBound($array) - 1
                        Local $right = "", $left = ""
                        If $k > UBound($array) - 1 Then ContinueLoop
;~
                        If StringInStr($array[$n], $array[$k]) Then ;Or StringInStr($array[$k],$array[$n]) Then
                                _ArrayDelete($array, $k)
                                        Return simplified($array)
                        ElseIf StringInStr($array[$k], $array[$n]) Then
                                _ArrayDelete($array, $n)
                                        Return simplified($array)
                                Else
;~                                         _ArrayDisplay($array,$long)
                                If (StringRegExp($array[$n], '\b' & $long & '\w+\b', 0) Or StringRegExp($array[$n], '\b\w+' & $long & '\b', 0)) And _
                                                (StringRegExp($array[$k], '\b' & $long & '\w+\b', 0) Or StringRegExp($array[$k], '\b\w+' & $long & '\b', 0)) Then
;~                                         $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b' & $long & '\w+\b', 1)
;~                                         If Not @error Then $left = $temp[0]
;~                                         
;~                                         $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b\w+' & $long & '\b', 1)
;~                                         If Not @error Then $right = $temp[0]
;~                                         
;~                                         $array[$n] = $right & StringReplace($left, $long, "")
                                        $temp0 = StringRegExpReplace($array[$n] &";"& $array[$k], '(\w+)(?=;\1)', '')                                        
                                        $temp1 = StringRegExpReplace($array[$k] &";"& $array[$n], '(\w+)(?=;\1)', '')
                                        If StringLen($temp0)<StringLen($temp1) Then
                                                $array[$n] =StringReplace($temp0,";","")
                                                _ArrayDelete($array, $k)
;~                                                 _ArrayDisplay($array)
                                                Return simplified($array)
                                        Else
                                                $array[$n] =StringReplace($temp1,";","")
                                                _ArrayDelete($array, $k)
;~                                                 _ArrayDisplay($array)
                                                Return simplified($array)
                                        EndIf        
                                EndIf
                        EndIf
                Next
        Next
        Return $array
EndFunc   ;==>simplified
回复

举报

3mile
发表于 2011-12-8 17:42:48 | 显示全部楼层
换个思路看下
#include <Array.au3>

;~ Local $aArray[4] = ["abcde", "abcd", "abc","abs"];['gga', 'bcde', 'abc']
Local $aArray[3] = ['gga', 'bcde', 'abc']
;~ Local $aArray[3] = ["bc", "ca", "a"]
;~ Local $aArray[6] = ["cabe", "bef", "abex","ca","be","efx"]

Local $k=1
$aNewArray = _ArrayPermute($aArray, ",") ;使用默认参数

For $i=1 To UBound($aNewArray)-1
        $aNewArray[$i]=StringRegExpReplace($aNewArray[$i],'(\w+)(?=,\1)','')
        $aNewArray[$i]=StringFormat('%010s',StringReplace($aNewArray[$i],",",""))        
Next

_ArraySort($aNewArray,0,1)

For $i=1 To UBound($aNewArray)-2
        $aNewArray[$i]=StringRegExpReplace($aNewArray[$i],'^0+','')
        $aNewArray[$i+1]=StringRegExpReplace($aNewArray[$i+1],'^0+','')
        ConsoleWrite(StringLen($aNewArray[$i])&@TAB&StringLen($aNewArray[$i+1])&@CRLF)
        If StringLen($aNewArray[$i])=StringLen($aNewArray[$i+1]) Then 
                $k+=1
        Else
                ExitLoop
        EndIf
Next

$out=_ArrayToString($aNewArray,@CRLF,1,$k)
MsgBox(0,0,$out)
回复

举报

lixiaolong
发表于 2011-12-9 04:44:44 | 显示全部楼层
来学习了！
回复

举报

menfan1
发表于 2011-12-14 09:22:37 | 显示全部楼层
看看啥内容哈
回复

举报

下一页 »
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 加入

本版积分规则

QQ|手机版|小黑屋|AUTOIT CN ( 鲁ICP备19019924号-1 )谷歌 百度

GMT+8, 2024-5-16 03:41 , Processed in 0.103112 second(s), 31 queries .

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表