您的位置：程序门 -> vb -> 资源



求一时间复杂度较小的容错的子串算法


[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]


求一时间复杂度较小的容错的子串算法[已结贴,结贴人:tyeken8]
发表于：2007-03-26 12:47:32 楼主
问题描述:
有一字符串数组a（)（只有小写字母和数字）
如
a（1)= "asdfghjkljwpef "
a（2)= "asdoghjklaoiefna "
a（3)= "asdoehjklajsldkfj "
用一个字符串s= "sdfgh "匹配（容差一个字符）
则a（1)与a（2)被选中（无需返回子串位置）
可以对字符数组做预处理（时间不算在内）

貌似就是这么多了，我现在想要一个此问题的算法，望各位专家不吝赐教，吾不胜受恩感激！
发表于：2007-03-26 13:21:301楼 得分:5
private   sub   command1_click（)
        dim   a（3)   as   string
        dim   i   as   integer
       
        a（1)   =   "asdfghjkljwpef "
        a（2)   =   "asdoghjklaoiefna "
        a（3)   =   "asdoehjklajsldkfj "
       
        for   i   =   1   to   3
                if   a（i)   like   "*sd?gh* "   then   debug.print   "a（ "   &   i   &   ")被选中 "
        next
       
end   sub
发表于：2007-03-26 13:36:112楼 得分:0
貌似不对啊，通配符的位置不确定阿...
发表于：2007-03-26 13:42:313楼 得分:10
function   likeex（byval   ssub   as   string,   byval   sdata   as   string)   as   boolean
        dim   iloop   as   integer
        likeex   =   false
        for   iloop   =   1   to   len（ssub)
                if   sdata   like   "* "   &   left（ssub,   iloop   -   1)   &   "? "   &   mid（ssub,   iloop   +   1)   &   "* "   then
                        likeex   =   true
                        exit   for
                end   if
        next   iloop
end   function

private   sub   form_load（)
        dim   a（2)   as   string
        dim   iloop   as   integer
       
        a（0)   =   "asdfghjkljwpef "
        a（1)   =   "asdoghjklaoiefna "
        a（2)   =   "asdoehjklajsldkfj "
       
        for   iloop   =   0   to   2
                if   likeex（ "sdfgh ",   a（iloop))   then   debug.print   "a（ "   &   iloop   +   1   &   ")被选中 "
        next
        end
end   sub
发表于：2007-03-26 17:45:414楼 得分:0
哦？
那么这个算法的事件复杂度是多少呢？
发表于：2007-03-26 17:50:245楼 得分:0
o（n)
发表于：2007-03-26 20:15:326楼 得分:0
请问你，n是什么意思呢？
不要随便写个式子糊弄我...
发表于：2007-03-27 13:15:377楼 得分:0
其实可以写一个类似于kmp的算法
发表于：2007-03-27 13:38:068楼 得分:5
请问你，n是什么意思呢？
不要随便写个式子糊弄我...

无语...
楼主你先弄明白时间复杂度表达式的含义,   好不好?
n是问题规模，在这里，可以认为就是数组a的元素个数
发表于：2007-03-27 17:55:189楼 得分:0
·—·貌似真的是哦
一重循环
发表于：2007-03-27 17:58:2810楼 得分:0
但是只能够容错一个字符阿，我还是自己想想吧...
发表于：2007-03-27 18:24:3911楼 得分:0
恩，刚才我想出一个算法，各位看看怎么样
function   fmodel（main   as   string,   pattern   as   string,   cfault   as   integer)   as   boolean
        fmodel   =   false
        for   i   =   1   to   len（main)   -   len（pattern)
                fault   =   0
                for   j   =   1   to   len（pattern)
                        if   mid$（main,   i   +   j   -   1,   1)   <>   mid$（pattern,   j,   1)   then   fault   =   fault   +   1
                        if   fault   >   cfault   then   exit   for
                next
                if   fault   <=   cfault   then   fmodel   =   true:   exit   for
        next
end   function

相关文章
其他资讯

快速检索
分类导航标签a

最新资讯
热门点击