📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3930| 回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

微软面试,查找第一次出现的最长重复子串

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
因为不到100积分,这里分享一下前阵子微软面试的题目。
前阵子微软面试的题目,一个阿三面的,问如何在一个字符串里面查找第一次出现的最长的重复子串。如:banana,返回an(这里重复不计)。我当时的想法是,在前面遍历所有的子串,然后在剩下的部分里面用
KMP查找是否存在,这样遍历前面的所有子串的复杂度是N2,后面匹配的复杂度是N,这样总的复杂度是N3。
写了代码,然后就gg思密达了。
后来回来想想,有两种方法可以做这个题。但是最主要的还是要想到用后缀,以前看算法的时候觉得这个没什么就没看,
现在遇到了就后悔了。
思路:
第一种思路就是根据KMP算法中求next数组的算法,对每一个后缀求next然后求最大值,但是这里不能重复要处理一下的。
第二种思路就是构建后缀树,后缀树的组织形式可以通过trie树来组织。
两种做法的复杂度都是N2的复杂度。
感觉第二种比较直观,也比较容易想到。这里分享一下后缀树,后缀数组的讲义。(之前没看这个真后悔)
后缀数组号称可以解决字符串中的所有问题。建议大家看看。 suffix-array.pdf (247.7 KB, 下载次数: 132)


评分

参与人数 4大米 +76 收起 理由
hellosniper + 3 很有用的信息!
tacit + 3 感谢分享!
edussx + 10 感谢分享!
加州刺史白十五 + 60

查看全部评分


上一篇:求问一个关于用函数产生linked list的问题
下一篇:amazon online test
全局:
楼主可以把面经写的详细一些,就这一道题目?电面吗
回复

使用道具 举报

🔗
jason51122 2013-10-3 12:36:48 | 只看该作者
全局:
后缀树确实比kmp好用 之前m还考kmp 没想到现在已经考到后缀树了 不会acm表示压力很大
回复

使用道具 举报

🔗
slowbull 2013-10-3 14:40:40 | 只看该作者
全局:
研究过两个月后缀数组感觉对这种问题真是好用啊。
回复

使用道具 举报

🔗
leseryang 2013-10-10 01:15:12 | 只看该作者
全局:
不知道会不会真的考到后缀树,我觉得面试一个小时以内写完很悬啊。。。
回复

使用道具 举报

🔗
pla1988 2013-10-22 11:57:51 | 只看该作者
全局:
本帖最后由 pla1988 于 2013-10-22 12:24 编辑

直接后缀数组排序(new 一个指针数组分别指向字符串的每一个元素,然后qsort),再求出最大的相邻两项的公共前缀长度和他们长度差值之间的min时间复杂度O(n2),空间复杂度O(n)
回复

使用道具 举报

🔗
hno3 2013-10-25 11:17:53 | 只看该作者
全局:
好东西 真是 来顶一下
回复

使用道具 举报

🔗
adlxk 2013-10-27 06:43:35 | 只看该作者
全局:
suffix array的确很好用。。但是这题要求有点没看懂,楼主说“这里重复不计”的意思是像ana这样的重复子串不能算?是不是说重复出现的例子不能有重叠的
回复

使用道具 举报

🔗
astray1988 2013-11-6 13:23:49 | 只看该作者
全局:
thx for sharing~
回复

使用道具 举报

🔗
乔克 2013-11-9 13:37:46 | 只看该作者
全局:
我怎么下载不了楼楼给的那个后缀算法
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表