题目：给定一组字符串，要求求出一个最短的字符串：使得它包含所有给出的字符串-『提问交流』-AUTOIT CN

happytc 发表于 2011-12-7 23:52:40

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

例如：比如"a","bc","ca"，那么应该得到字符串是"bca"

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

看看那个的算法最好！

afan 发表于 2011-12-8 01:31:19

字符数应该可以确定，不过位置似乎有多样性~ 比如第二个例子 befcabex 应该也符合条件…

happytc 发表于 2011-12-8 02:48:04

回复 2# afan

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

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

原题目：
===============================================
Name: Shortest Common Superstring 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 http://www.autoitx.com/images/common/back.gif

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

我的思路是：
设字串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 = ["cabe", "bef", "abex"]
$fin=simplified($str)
$t=_ArrayToString($fin,"")
MsgBox(0,0,$t)

Func simplified($str)
Local $flag_array, $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
$flag_array = $flag
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

$temp = StringRegExp($str[$n] & @CRLF & $str[$k], '\b\w+' & $new[$i] & '\b', 1)
If Not @error Then $right = $temp

;~ 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

3mile 发表于 2011-12-8 14:27:23

本帖最后由 3mile 于 2011-12-8 14:47 编辑

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

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

Func simplified($array)
Local $flag_array, $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
$flag_array = $flag
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
;~
;~ $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b\w+' & $long & '\b', 1)
;~ If Not @error Then $right = $temp
;~
;~ $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

afan 发表于 2011-12-8 16:04:15

貌似还有问题，再来：
3mile 发表于 2011-12-8 14:27 http://www.autoitx.com/images/common/back.gif

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

afan 发表于 2011-12-8 16:15:59

本帖最后由 afan 于 2011-12-8 21:04 编辑

以下为我的题解，还可以得到所有符合条件的组合：
**** Hidden Message *****

3mile 发表于 2011-12-8 16:35:21

再来
#include <array.au3>
Global $out

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

Func simplified($array)
Local $flag_array, $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
$flag_array = $flag
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
;~
;~ $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b\w+' & $long & '\b', 1)
;~ If Not @error Then $right = $temp
;~
;~ $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 = ["abcde", "abcd", "abc","abs"]
;~ Local $str = ["bc", "ca", "a"]
Local $str = ["cabe", "bef", "abex","ca","be","efx"]
;~ Local $str = ['gga', 'bcde', 'abc']
_ArraySort($str)

$fin = simplified($str)
;~ _ArrayDisplay($fin)
$t = _ArrayToString($fin, "")
MsgBox(0, TimerDiff($ts), $t)

Func simplified($array)
Local $flag_array, $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
$flag_array = $flag
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
;~
;~ $temp = StringRegExp($array[$n] & @CRLF & $array[$k], '\b\w+' & $long & '\b', 1)
;~ If Not @error Then $right = $temp
;~
;~ $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 = ["abcde", "abcd", "abc","abs"];['gga', 'bcde', 'abc']
Local $aArray = ['gga', 'bcde', 'abc']
;~ Local $aArray = ["bc", "ca", "a"]
;~ Local $aArray = ["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

看看啥内容哈

页: [1] 2

AUTOIT CN's Archiver

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