西西软件园多重安全检测下载网站、值得信赖的软件下载站!
软件
软件
文章
搜索

首页编程开发其它知识 → 兄弟字符串怎么判断、如何迅速匹配兄弟字符串?

兄弟字符串怎么判断、如何迅速匹配兄弟字符串?

相关软件相关文章发表评论 来源:圣歌时间:2011/12/25 2:40:40字体大小:A-A+

作者:圣歌点击:178次评论:18次标签: 字符串

  • 类型:电子教程大小:9.5M语言:中文 评分:8.0
  • 标签:
立即下载

如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,问如何迅速匹配兄弟字符串?

首先:接到题目,匹配字符串,这不简单了,遍历嘛。。
方法一:
步骤如下:
  1.判断两个字符串的长度是否一样。
  2.循环提取第一个字符串的字符去第二个字符串中寻找是否存在?
  3.全部都有则是兄弟字符串,其他则不是兄弟字符串。

时间复杂度N*N/2 ,平方级。
额,这算法真的就正确么??????
来看看这种情况:字符串A为aab;字符串B为abc,一看就知道它们是false,那按照上面我写的算法得出的结论却是true。
上面的算法错误的,考虑不周,那以遍历这种思路到底是否能判断兄弟字符串?
能,只要把上面的算法第2步稍微改动一下,改为“2.循环提取第一个字符串的字符去第二个字符串中寻找是否存在?存在则移除第二个字符串中的那个字符。”
好了,遍历思路算是可以解决了这个问题了。
不过嘛,遍历思路的时间复杂度是指数级,太耗时间,性能不好。

方法二:
赋予字符额外的意义。什么意思了,给26个字符依次赋予质数。质数是比较特殊的一堆数字,它们只能被1和本身整除。
给a赋值2、给b赋值3、给c赋值5、给d赋值7、给e赋值11、给f赋值13 等等……
好了,给两个字符串中的所有字符都赋值了,,接着让它们各自相加,如果两个字符串得出的结果是一样的,那它们是兄弟字符串。。
嘎嘎,时间复杂度是常数。性能好了是不????
别太高兴了,这个算法到目前为止也是有问题的,来看看这种情况:bf和ce不是兄弟字符串,按照上面的赋值规律b+f=3+13=16;c+e=5+11=16 ,看吧,明明他们就不是兄弟字符串,但是按照上面的算法就错了。
怎么解决这个问题了?用乘积:每个字符串内部求乘积,相等就是兄弟字符串。
好了,这算法是正确的,但是呢,又有个算法外的问题:字符串相乘及其容易出现结果溢出,说得简单点就是乘积太大了,大于程序语言的内置的整数类型(int、long)所能表示的最大值。这怎么解决?有个比较偏的方法就是用数组来存储乘积。具体方法我不说了,跟本偏文章无关。。。
那怎么解决兄弟字符串的问题???用平方和或者立方和。。。。。既然直接用加法不行,用乘法还会溢出。那换个思路用平方和。。。
b*b+f*f=3*3+13*13=178;c*c+e*e=5*5+11*11=146
看吧它们不是兄弟字符串吧。。。。。


这只是我的算法思路,可能有误,仅供参考。。。。

@万仓一黍
你说的思路能行,但是这两个数组该如何实现????
首先,数组是种键值对,而常用的编程语言(C、C++、C#、java)中数组的键都是数字,你说得用数组记录字符串中的各个字符出现的次数该如何操作??????
ascii编码表不是有编码0到255总共256个字符,声明2个长度为256的一维数组,把两个字符串中的字符转换为ascii表中的编码后,之后在对应的数组单元中加1,最后对比两个数组。

额,另外,用哈希表是否可以实现?对哈希表不太了解,不好判断。。。
用数组实现,很简单的。定义两个数组a(255),b(255)
遍历两个字符串,遇到字符的时候,直接利用该字符的Ascii码来获得在数组中的位置。如a(asc(char))++

    相关评论

    阅读本文后您有什么感想? 已有人给出评价!

    • 8 喜欢喜欢
    • 3 顶
    • 1 难过难过
    • 5 囧
    • 3 围观围观
    • 2 无聊无聊

    热门评论

    最新评论

    发表评论 查看所有评论(18)

    昵称:
    表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
    字数: 0/500 (您的评论需要经过审核才能显示)