文档章节

一道2015阿里校招系统工程师笔试代码题

好铁
 好铁
发布于 2014/09/21 15:38
字数 516
阅读 42
收藏 0
问题:给定一个query和一个text,均由小写字母组成,要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如,query为"acbac",text为"acaccbabb",那么text中的"cba"为最长的连续出现在query中的字母序列,因此,返回结果应该为其长度3,请注意程序效率。


在线笔试时没做出来,后来做了一下:
#include<stdio.h>
#include<string.h>

#define MAXLEN 1024

int max_sub_len(char *s, char *p);
int kmp_max_sub_len(char *s, char *p);
void get_next(char *str, int next[]);

char text[] = "acaccbabb";
char query[] = "acbac";

int main()
{
	int length;
	length = kmp_max_sub_len(text, query);
	//length = max_sub_len(text, query);
	printf("%d\n", length);
	return 0;
}

int max_sub_len(char *s, char *p)
{
	int s_len = strlen(s);
	int p_len = strlen(p);
	int max = 0;

	int i, j, k;
	for (k = 0; k < p_len; k++) {
		i = 0;
		j = 0;
		while (i < s_len && j < p_len - k) {
			if (s[i] == p[j + k]) {
				i++;
				j++;
				max = (max < j) ? j : max;
			} else {
				i = i - j + 1;
				j = 0;
			}
		}
	}
	return max;
}


void get_next(char *str, int next[])
{
	int i, j;
        int length=strlen(str);

	i = 0;
        j=1;
	next[0] = 0;
        while(j<length){
            if(str[i]==str[j]){
                next[j]=next[j-1]+1;
                i++;
                j++;
            }else{
                next[j]=0;
                j++;
                i=0;
            }
        }

}
int kmp_max_sub_len(char *s, char *p)
{
	int s_len = strlen(s);
	int p_len = strlen(p);
	int max = 0;
        int next[MAXLEN];
        char *n;

	int i, j, k;
	for (k = 0; k < p_len; k++) {
		i = 0;
		j = 0;
                n=p+k;
                get_next(n,next);
		while (i < s_len && j < p_len - k) {
			if (s[i] == p[j + k]) {
				i++;
				j++;
				max = (max < j) ? j : max;
			} else {
				i = i + j - next[j]+1;
				j = 0;
			}
		}
	}
	return max;
}



其中max_sub_len为朴素模式匹配,若text长度为m,所查询的query长度为n,则复杂度为O(m* n  * n);
kmp_max_sub_len使用了kmp算法,复杂度为O((m+n) * n)).

这个题目由于搜索模式是可变的,不再是单纯的kmp算法了,增加了n!这部分的复杂度,不知道这里是否还可以优化。


关于kmp算法,有两篇很好的文章:
一个在这
另一个在这


附注:后来查了下,寻找最长公共字串,属于动态规划,上面的解法可能不好。以前没学习这个,以后再来改

© 著作权归作者所有

好铁
粉丝 40
博文 266
码字总数 78926
作品 0
朝阳
程序员
私信 提问
90 道名企笔试和算法题 (含答题讨论)

(点击上方公众号,可快速关注) 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问:如何获取题目列表? 答:① 长摁二维码关注「算法爱好者」,② 然后给它发送 名企笔试 或 算法...

Python开发者
2018/01/21
0
0
前端笔试、面试

让 BAT 的 Offer 不再难拿 随着各大公司春招的开始,很多小伙伴都行动起来了,我有幸能够加入百度并和大家分享自己的经验心得。由于我面试的都是比较大的公司,所以自然也是做了这方面的准备...

掘金官方
2018/01/11
0
0
18届清华硕士狂拿18家互联网公司offer

2018校招总结(外企,国内大公司,国内创业公司) 本篇是我参加2018春招实习和秋招的求职经历,除了笔试面试中遇到的一些问题,更多的是一些个人想法。 春招和秋招面了不少公司,实习offer有...

野梦M
2017/12/18
0
1
一条咸鱼的校招之路

一条咸鱼的校招之路 [TOC] 又是一年一度的秋招,作为某不知名211高校的菜鸟渣渣而言,想进一家靠谱点的大公司真是很艰难的。 这里写图片描述 梦想总是要有的,万一实现了呢?抱着试一试的心态...

窗边的扁豆
2017/10/01
0
0
九月十月百度,迅雷,华为,阿里巴巴最新校招笔试面试二十题(10.12)

九月十月百度,迅雷,华为,阿里巴巴,最新校招笔试面试二十题 题记 本博客自2010年10月11日开通以来,已经帮助了一大批人找到工作,特别是连续三年在每一年的9、10月份陪伴了至少三届毕业生...

mickelfeng
2013/10/12
244
0

没有更多内容

加载失败,请刷新页面

加载更多

PostgreSQL 11.3 locking

rudi
今天
5
0
Mybatis Plus sql注入器

一、继承AbstractMethod /** * @author beth * @data 2019-10-23 20:39 */public class DeleteAllMethod extends AbstractMethod { @Override public MappedStatement injectMap......

一个yuanbeth
今天
12
1
一次写shell脚本的经历记录——特殊字符惹的祸

本文首发于微信公众号“我的小碗汤”,扫码文末二维码即可关注,欢迎一起交流! redis在容器化的过程中,涉及到纵向扩pod实例cpu、内存以及redis实例的maxmemory值,statefulset管理的pod需要...

码农实战
今天
4
0
为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接?

之前在阅读《阿里巴巴Java开发手册》时,发现有一条是关于循环体中字符串拼接的建议,具体内容如下: 那么我们首先来用例子来看看在循环体中用 + 或者用 StringBuilder 进行字符串拼接的效率...

武培轩
今天
9
0
队列-链式(c/c++实现)

队列是在线性表功能稍作修改形成的,在生活中排队是不能插队的吧,先排队先得到对待,慢来得排在最后面,这样来就形成了”先进先出“的队列。作用就是通过伟大的程序员来实现算法解决现实生活...

白客C
今天
81
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部