想了很久,可还是做不出!题目如下:
给定一组字符串,要求求出一个最短的字符串使得它包含所有给出的字符串。
比如"a","bc","ca".输出应该是"bca".
为不至进入迷区,再举过例子:cabe", "bef", "abex",这三个字串中,输出结果应该是:cabexbef.为了更好地让大家明白再举例子:如("acb","acbbc","ef"),应输出"acbbcef"
("bbf","fbb","acbb"),应输出"acbbfbb"而不是"fbbfacbb"
("abc","def","hij"),应输出"abcdefhij"<注意了,是最短的字串>
速度至上,代码的可读性也要好,附上适当的注释!能用正则表达式吗?如能,要怎样做?
给定一组字符串,要求求出一个最短的字符串使得它包含所有给出的字符串。
比如"a","bc","ca".输出应该是"bca".
为不至进入迷区,再举过例子:cabe", "bef", "abex",这三个字串中,输出结果应该是:cabexbef.为了更好地让大家明白再举例子:如("acb","acbbc","ef"),应输出"acbbcef"
("bbf","fbb","acbb"),应输出"acbbfbb"而不是"fbbfacbb"
("abc","def","hij"),应输出"abcdefhij"<注意了,是最短的字串>
速度至上,代码的可读性也要好,附上适当的注释!能用正则表达式吗?如能,要怎样做?
用Dictionary对象,用mid把每个字符串的字符存入Dictionary,存入时用exist属性判断是否存在,存在的话就不添加,否则add,然后For i = 0 To Dictionary.Count -1,把所有的对象连起来就可以了
以下是全排列程序,仅供参考:Dim iStr(), ii As LongPrivate Sub Command1_Click()
Dim a(), b, c, i, d
Dim in1, in2, in3
in1 = "a": in2 = "bc": in3 = "ca" '比如"a","bc","ca".输出应该是"bca".
'in1 = "cabe": in2 = "bef": in3 = "abex" 'cabe", "bef", "abex",这三个字串中,输出结果应该是:cabexbef.
b = in1 & in2 & in3
c = Len(b) - 1
ReDim a(c)
For i = 0 To c
a(i) = Mid(b, i + 1, 1)
Next
pai a, 0, c + 1
For j = 1 To Len(b)
For i = 0 To UBound(iStr)
If InStr(iStr(i), in1) <> 0 And InStr(iStr(i), in2) <> 0 And InStr(iStr(i), in3) <> 0 Then
d = Mid(iStr(i), 1, j)
If InStr(d, in1) <> 0 And InStr(d, in2) <> 0 And InStr(d, in3) <> 0 Then
Debug.Print d
Exit Sub
End If
End If
Next
Next
End SubSub chang(a(), m As Integer)
Dim i As Integer, j As Integer
Dim temp As String
temp = a(0)
For i = 0 To m - 1
a(i) = a(i + 1)
Next
a(i) = temp
End SubSub pai(a(), m As Integer, n As Integer)
Dim k As Integer
If m < n Then
For k = 0 To m
pai a, m + 1, n
chang a, m
Next
Else
ReDim Preserve iStr(ii)
iStr(ii) = Join(a, "")
ii = ii + 1
DoEvents
End If
End Sub
Dim s As String, sTmp As String, sLeft As String, sRight As String, sLong As String
Dim sStrIn() As String
Dim i As Byte, l As Byte
's = "acb,acbbc,ef,b,cbb"
s = "bbf,fbb,acbb"
's = "a,bc,ca"
sStrIn = Split(s, ",") '赋值给数组
For i = 0 To UBound(sStrIn) '排序
For l = i To UBound(sStrIn)
If Len(sStrIn(i)) < Len(sStrIn(l)) Then
sTmp = sStrIn(i)
sStrIn(i) = sStrIn(l)
sStrIn(l) = sTmp
End If
Next l
'Debug.Print sStrIn(i)
Next isLong = sStrIn(0) '最长的赋值给母串
sLeft = sStrIn(0)
sRight = sStrIn(0)
For i = 1 To UBound(sStrIn) '把不包含的字符加到左边
If InStr(sLeft, sStrIn(i)) = 0 Then
For l = 1 To Len(sStrIn(i))
If InStr(Left(sLeft, Len(sStrIn(i)) - l), Right(sStrIn(i), l)) Then
sLeft = Left(sStrIn(i), Len(sStrIn(i)) - l) & sLeft
End If
If l = Len(sStrIn(i)) Then sLeft = sStrIn(i) & sLeft
Next l
End If
Next iFor i = 1 To UBound(sStrIn) '把不包含的字符加到右边
If InStr(sRight, sStrIn(i)) = 0 Then
For l = 1 To Len(sStrIn(i))
If InStr(Right(sRight, Len(sStrIn(i)) - l), Left(sStrIn(i), l)) Then
sRight = Right(sStrIn(i), Len(sStrIn(i)) - l) & sRight
End If
If l = Len(sStrIn(i)) Then sRight = sRight & sStrIn(i)
Next l
End If
Next i
If Len(sRight) < Len(sLeft) Then sLong = sRight Else sLong = sLeft '取最短的
Debug.Print "L:" & sLeft & " R:" & sRight & "最终:" & sLong
End Sub这个代码能正确实现你例程里的字符串。但是估计有其他特殊情况,请测试。
一本全面彻底讲解字符串查找算法的书。 书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有进一步的参考文献。 一本研究字符串查找算法不容错过的好书。
Dim col As New Collection
Call col.Add("a")
Call col.Add("bc")
Call col.Add("ca")
Debug.Print FindMinCouple(col)
Call clear(col)
Call col.Add("cabe")
Call col.Add("bef")
Call col.Add("abex")
Debug.Print FindMinCouple(col) Call clear(col)
Call col.Add("acb")
Call col.Add("acbbc")
Call col.Add("ef")
Debug.Print FindMinCouple(col) Call clear(col)
Call col.Add("bbf")
Call col.Add("fbb")
Call col.Add("acbb")
Debug.Print FindMinCouple(col) Call clear(col)
Call col.Add("abc")
Call col.Add("def")
Call col.Add("hij")
Debug.Print FindMinCouple(col)
End SubPrivate Sub clear(ByVal col As Collection)
Dim i As Long
For i = 1 To col.Count
Call col.Remove(1)
Next
End Sub
'---------------------------------------------------------------------------------------
' 过程名称: FindMinCouple
' 过程作者: sonic_andy
' 创建日期: 2010/1/24
' 实现功能: 获取最小长度的组合字符串
' 参数 col: 源串集合
' 返回值: 得到的最小组合
'---------------------------------------------------------------------------------------
Private Function FindMinCouple(ByRef col As Collection) As String
' 获取直接拼接的字符串
Dim i As Long
For i = 1 To col.Count
FindMinCouple = FindMinCouple & col(i)
Next
Call Combine(col, 2, col(1), FindMinCouple)
End Function'---------------------------------------------------------------------------------------
' 过程名称: Combine
' 过程作者: sonic_andy
' 创建日期: 2010/1/24
' 实现功能: 递归组合所有可能的情况
' 参数 colSrc: 源串集合
' 参数 lngDepth: 递归深度
' 参数 strCombined: 上一步组合好的字符串
' 参数 strResult: 最短字符串
'---------------------------------------------------------------------------------------
Private Sub Combine(ByRef colSrc As Collection, _
ByVal lngDepth As Long, _
ByVal strCombined As String, _
ByRef strResult As String)
' 如果已经组合了所有源串,则开始比较结果
If lngDepth > colSrc.Count Then
If Len(strCombined) < Len(strResult) Then
strResult = strCombined
End If
Exit Sub
End If
' 本次需要被加入的字符串
Dim strCurrent As String
strCurrent = colSrc(lngDepth)
' B=strCombined
' A=strCurrent
' BAB包含
Dim lngPos As Long
lngPos = InStr(1, strCombined, strCurrent)
If lngPos > 0 Then
Call Combine(colSrc, lngDepth + 1, strCombined, strResult)
End If
' ABA包含
lngPos = InStr(1, strCurrent, strCombined)
If lngPos > 0 Then
Call Combine(colSrc, lngDepth + 1, strCurrent, strResult)
End If
Dim lngCurrentLength As Long
lngCurrentLength = Len(strCurrent)
Dim lngCombinedLength As Long
lngCombinedLength = Len(strCombined)
Dim lngMinLength As Long
If lngCombinedLength < lngCurrentLength Then
lngMinLength = lngCombinedLength
Else
lngMinLength = lngCurrentLength
End If
Dim i As Long
For i = 1 To lngMinLength - 1
' AB重合
If Right(strCurrent, i) = Left(strCombined, i) Then
Call Combine(colSrc, _
lngDepth + 1, _
strCurrent & Right(strCombined, lngCombinedLength - i), _
strResult)
End If
' BA重合
If Right(strCombined, i) = Left(strCurrent, i) Then
Call Combine(colSrc, _
lngDepth + 1, _
strCombined & Right(strCurrent, lngCurrentLength - i), _
strResult)
End If
Next
' 不重合
Call Combine(colSrc, lngDepth + 1, strCurrent & strCombined, strResult)
Call Combine(colSrc, lngDepth + 1, strCombined & strCurrent, strResult)
End Sub
'---------------------------------------------------------------------------------------
' 过程名称: Combine
' 过程作者: sonic_andy
' 创建日期: 2010/1/24
' 实现功能: 递归组合所有可能的情况
' 参数 colSrc: 源串集合
' 参数 lngDepth: 递归深度
' 参数 strCombined: 上一步组合好的字符串
' 参数 strResult: 最短字符串
'---------------------------------------------------------------------------------------
Private Sub Combine(ByRef colSrc As Collection, _
ByVal lngDepth As Long, _
ByVal strCombined As String, _
ByRef strResult As String)
If Len(strCombined) >= Len(strResult) Then
Exit Sub
End If ' 如果已经组合了所有源串,则开始比较结果
If lngDepth > colSrc.Count Then
strResult = strCombined
Exit Sub
End If
' 本次需要被加入的字符串
Dim strCurrent As String
strCurrent = colSrc(lngDepth)
' B=strCombined
' A=strCurrent
' BAB包含
Dim lngPos As Long
lngPos = InStr(1, strCombined, strCurrent)
If lngPos > 0 Then
Call Combine(colSrc, lngDepth + 1, strCombined, strResult)
End If
' ABA包含
lngPos = InStr(1, strCurrent, strCombined)
If lngPos > 0 Then
Call Combine(colSrc, lngDepth + 1, strCurrent, strResult)
End If
Dim lngCurrentLength As Long
lngCurrentLength = Len(strCurrent)
Dim lngCombinedLength As Long
lngCombinedLength = Len(strCombined)
Dim lngMinLength As Long
If lngCombinedLength < lngCurrentLength Then
lngMinLength = lngCombinedLength
Else
lngMinLength = lngCurrentLength
End If
Dim i As Long
For i = 1 To lngMinLength - 1
' AB重合
If Right(strCurrent, i) = Left(strCombined, i) Then
Call Combine(colSrc, _
lngDepth + 1, _
strCurrent & Right(strCombined, lngCombinedLength - i), _
strResult)
End If
' BA重合
If Right(strCombined, i) = Left(strCurrent, i) Then
Call Combine(colSrc, _
lngDepth + 1, _
strCombined & Right(strCurrent, lngCurrentLength - i), _
strResult)
End If
Next
' 不重合
Call Combine(colSrc, lngDepth + 1, strCurrent & strCombined, strResult)
Call Combine(colSrc, lngDepth + 1, strCombined & strCurrent, strResult)
End Sub
似乎可以这样解:假设你有 n 个需要合并的元素,我们称之为 n 元问题。n > 1。第一步:简单降元。首先取最长的一个(称为母元素),循环遍历其他 n - 1 个元素(成为子元素),看是否有任意一个子元素完整包含于母元素。用 InStr 即可。如果找到这样的子元素,即消除该子元素,当作 n - 1 元问题来处理(n = n - 1)。如果 n 已经等于 1,则已经得解。否则仍从简单降元开始处理。第二步:
从最短的子元素开始遍历,将其前导和后缀于母元素,得到一个更长的串。分别遍历剩余的子元素,看是否包含。注意,不要找到一个包含子元素就跳出。要记录被包含的元素,及其总长度。结果分四种情况:1 仅前导或后缀得到包含,则该长串是新的母元素,消除被包含者。
2 如果前导和后缀均得到包含,比较包含总长度,取其长者。如前处理。
3 没有包含。则测试下一个子元素与母元素合并。直至全部遍历,如果没有包含,将剩余子元素与母元素全部合并,顺序无关。此解法不一定能得到最佳解,但得到较优解是没有问题的。
cabe -> bef : -2
bef -> cabe : 0
cabe -> abex : -3
abex -> cabe : 0
bef -> abex : 0
abex -> bef : 0
然后问题就变成了在有向图中找一条经过所有节点并且每个节点只经过一次的最短路径,这是个讨论得非常多的典型算法问题了。
S(25),0是A,依次表示26个字母.
如果有A字母,S(0)=1
最后把值是1的拼接起来就OK了.