骆驼爱吃巧克力

趋势科技2011校园招聘的一道编程笔试题

题目：编写一个函数int search(char *text)，text为输入的字符串，从字符串中找出一个最长的不含重复字符的子字符串，例如“axdbx”,返回4，子字符串为“axdb”，而“axdbxce”,返回5，子字符串为“dbxce”。

以下是我的答案，当然，较当时答题时的答案少有改动，但思路是一样的，毕竟答题时没有环境让我去debug。该算法时间复杂度为O(n)。并且不需要反复重置pos数组，每次访问到重新赋值即可。

#include < iostream.h>
#include < string.h> 

int search(char *text)
{
	int pos[128]; //用于记录字符最近一次出现的位置，使用ASC码做索引
	int maxL = 0;   //记录最大长度
	int start = 0;   //记录连续字符串的起始位置
	int end = strlen(text), i, tL;  //end为字符串text上界
	for (i=0; i<128; i++) pos[i] = -1;  //为每个字符初始化位置
	
	for (i=0; i
[......]
继续阅读
				

      如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。
      我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两[......]

继续阅读