中文XML论坛--问一个算法的题目！请高手指点！

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> We choose to study algorithmic problems, not because they are easy, but because they are hard.

[返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『算法理论与分析』 → 问一个算法的题目！请高手指点！

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 28778 个阅读者　　

*	贴子主题：问一个算法的题目！请高手指点！	举报打印推荐 IE收藏夹
	本主题类别:

eyounx

  威望：9
  等级：大四(GRE考了1400分!)(版主)
  文章：272
  积分：1260
  门派：GOOGLEBBS.NET
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第11楼

写出来的意思是写算法出来，况且上面的完全看不懂
----------------------------------------------
member of LAMDA, CS, NJU
http://lamda.nju.edu.cn/
http://lamda.nju.edu.cn/yuy

2005/4/11 20:53:00

eyounx

  威望：9
  等级：大四(GRE考了1400分!)(版主)
  文章：272
  积分：1260
  门派：GOOGLEBBS.NET
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第12楼

不过，好歹要拿两个有点公共部分的字符串来比吧，123456789和abcdefghijklm会有重叠的部分？
----------------------------------------------
member of LAMDA, CS, NJU
http://lamda.nju.edu.cn/
http://lamda.nju.edu.cn/yuy

2005/4/11 20:55:00

xzjxu

  等级：大二期末(C++考了100分!)
  文章：119
  积分：448
  门派：XML.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第13楼

以下是引用eyounx在2005-4-11 20:55:32的发言：
不过，好歹要拿两个有点公共部分的字符串来比吧，123456789和abcdefghijklm会有重叠的部分？

呵呵,你能看懂就行了,写代码太麻烦

2005/4/11 21:39:00

eyounx

  威望：9
  等级：大四(GRE考了1400分!)(版主)
  文章：272
  积分：1260
  门派：GOOGLEBBS.NET
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第14楼

看不懂的说
----------------------------------------------
member of LAMDA, CS, NJU
http://lamda.nju.edu.cn/
http://lamda.nju.edu.cn/yuy

2005/4/11 21:51:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第15楼

以下是引用xzjxu在2005-4-11 21:39:21的发言：
[quote]以下是引用eyounx在2005-4-11 20:55:32的发言：
不过，好歹要拿两个有点公共部分的字符串来比吧，123456789和abcdefghijklm会有重叠的部分？
[/quote]
呵呵,你能看懂就行了,写代码太麻烦

eyounx的上一个帖子好像是说他没看懂。
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
- Bertrand Russell

2005/4/11 21:52:00

xzjxu

  等级：大二期末(C++考了100分!)
  文章：119
  积分：448
  门派：XML.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第16楼

重看了一下楼主的题目,看来是我看错题目了,sorry

2005/4/12 13:38:00

xzjxu

  等级：大二期末(C++考了100分!)
  文章：119
  积分：448
  门派：XML.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第17楼

用VB写的
Private Function lcs(s1 As String, s2 As String) As Integer
    Dim L1 As Integer, L2 As Integer, t As Integer
    L1 = Len(s1): L2 = Len(s2)
    If s1 = "" Or s2 = "" Then
        lcs = 0
        Exit Function
    End If
    lcs = 0
    For i = 1 To L1
        For j = 1 To L2
            If Mid(s1, i, 1) = Mid(s2, j, 1) Then
                lcs = lcs(Right(s1, L1 - i), Right(s2, L2 - j)) + 1
                Exit Function
            End If
        Next j
    Next i
End Function

2005/4/12 14:45:00

xzjxu

  等级：大二期末(C++考了100分!)
  文章：119
  积分：448
  门派：XML.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第18楼

好象还有错误!

以下是引用xzjxu在2005-4-12 14:45:17的发言：
用VB写的
Private Function lcs(s1 As String, s2 As String) As Integer
     Dim L1 As Integer, L2 As Integer, t As Integer
     L1 = Len(s1): L2 = Len(s2)
     If s1 = "" Or s2 = "" Then
         lcs = 0
         Exit Function
     End If
     lcs = 0
     For i = 1 To L1
         For j = 1 To L2
             If Mid(s1, i, 1) = Mid(s2, j, 1) Then
                 lcs = lcs(Right(s1, L1 - i), Right(s2, L2 - j)) + 1
                 Exit Function
             End If
         Next j
     Next i
End Function

2005/4/12 17:10:00

eyounx

  威望：9
  等级：大四(GRE考了1400分!)(版主)
  文章：272
  积分：1260
  门派：GOOGLEBBS.NET
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第19楼

我用dp写一段，你比比看：
dim dparray(1 to 1) as integer, L1 as integer, L2 as integer
function LCS( stra as string, strb as string) as integer
   dim i as integer
   L1 = len(stra) : L2 = len(strb)
   redim dparray(1 to L1*L2+L2)      '忘记二维数组了，就这样吧
   for i=1 to L1*L2+L2
      dparray(i) = -1
   next
   LCS = LCS_Sub(stra,strb,1,1)
end function
function LCS_Sub( stra as string, strb as string, indexa as integer, indexb as integer) as integer)
    if stra>L1 OR strb>L2 then
        LCS_Sub = 0
    else
        if dparray(indexa*L1+indexb)<0 then
            if mid(stra,indexa,1)=mid(strb,indexb,1) then
                dparray(indexa*L1+indexb) = 1 + LCS_Sub(stra,strb,indexa+1,indexb+1)
            else
                dim leftLen as integer, rightLen as integer
                leftLen = LCS_Sub(stra,strb,indexa+1,indexb)
                rightLen = LCS_Sub(stra,strb,indexa,indexb+1)
                if( leftlen > rightlen ) then
                    dparray(indexa*L1+indexb) = leftlen
                else
                    dparray(indexa*L1+indexb) = rightlen
                endif
            end if
        end if
        LCS_Sub = dparray(indexa*L1+indexb)
    end if
end function
我手上没有basic编译器，可能有语法错误。
----------------------------------------------
member of LAMDA, CS, NJU
http://lamda.nju.edu.cn/
http://lamda.nju.edu.cn/yuy

2005/4/12 17:35:00

xzjxu

  等级：大二期末(C++考了100分!)
  文章：119
  积分：448
  门派：XML.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第20楼

你那个数组用的罗嗦
看下面的
Private Sub Form_Click()
    Dim s1 As String, s2 As String
    s1 = text1: s2 = text2
    Print lcs(s1, s2)
End Sub
Private Function lcs(s1 As String, s2 As String) As Integer
    Dim L1 As Integer, L2 As Integer, L As Integer
    L1 = Len(s1): L2 = Len(s2)
    If s1 = "" Or s2 = "" Then
        lcs = 0
    Else
        If Mid(s1, 1, 1) = Mid(s2, 1, 1) Then
            lcs = lcs(Right(s1, L1 - 1), Right(s2, L2 - 1)) + 1
        Else
            L = lcs(Right(s1, L1 - 1), s2)
            lcs = lcs(s1, Right(s2, L2 - 1))
            If lcs < L Then lcs = L
        End If
    End If
End Function

2005/4/12 19:14:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/5/10 16:35:44

本主题贴数30，分页： [1] [2] [3]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	179.688ms