| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1357 人关注过本帖
标题:请教取得两个字符串相同部分的快速算法
只看楼主 加入收藏
zhipeng0117
Rank: 1
等 级:新手上路
帖 子:71
专家分:0
注 册:2005-9-15
收藏
 问题点数:0 回复次数:3 
请教取得两个字符串相同部分的快速算法
已知两个字符串,可以表示成string1=stringA+stringB,string2=stringA+stringC
用什么方法可以快速取出stringA呢,如果一个一个字符比较好像比较慢啊
搜索更多相关主题的帖子: 算法 字符 
2008-02-22 21:47
houyunqing
Rank: 1
等 级:新手上路
帖 子:476
专家分:0
注 册:2005-4-1
收藏
得分:0 
在unsafe中把string切成8字节一段一段的int类型的,切割的截止位置以短的那个string为标准
那么string1在内存中就可以为:intaintbincintd... (inta, intb, intc, intd都是int变量)
string2向类似为int2aint2bint2cint2d...
inta-int2a=0的话就代表这个部分完全相同
intb-int2b=0的话也代表这个部分相同
一直减到一个部分发现不等于零的话,就把那个差的绝对值以二分法对256^1~7进行比较从而可以找出开始不相同的那一位是哪一位,当然,如果你嫌这种找不同的方式太麻烦,那就直接在这个地方一位一位地对比就好了

你也可以以16字节为一段的int64为单位来进行对比,这样可以把需要的对比次数减半,但是当strings不够长的情况下这个没意义,或者你也可以把int32换成int16如果strings会很短
这个地方不可以使用double或者single来操作,因为它们的加减并不是直接按照高位到低位来进行的

unsafe嘛,参考一下这个。。。然后再参考点别的吧。。。其实这个方法主要是在string比较长的时候可能才会有用
https://bbs.bccn.net/viewthread.php?tid=26219&extra=page%3D5%26amp%3Bfilter%3Ddigest

寻求挑战,追求完美 Oh,my god!
2008-02-23 00:50
zhipeng0117
Rank: 1
等 级:新手上路
帖 子:71
专家分:0
注 册:2005-9-15
收藏
得分:0 
确实是一种选择
你提到的方法让我想起了Morton码
谢谢啦

2008-02-24 22:47
cobby
Rank: 1
等 级:新手上路
威 望:1
帖 子:565
专家分:0
注 册:2007-7-11
收藏
得分:0 
这个不是模式匹配算法吗?有一个KMP算法可以参考一下

努力成为菜鸟!
2008-02-25 08:28
快速回复:请教取得两个字符串相同部分的快速算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017327 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved