字符串的一些题

---------------------------------------------------------------------------

给定一个字符串，求其最长连续重复子串，如果有多个则返回第一个。例如 “ababc”要求返回“ab”，因为“ab”连续重复出现且最长。给出复杂度分析。

思路：设字符串长度为 len，从长度为 len/2 开始，递减测试，看是否有长度为 test 的重复连续字符串。

程序见下，时间复杂度为 O(n^3)。

#include <stdio.h>
#include <string.h>

int check(char * str, int s, int n)
{
int m = s + n;
while(str[s] == str[s + n] && s < m)
{
s++;
}
return s < m ? 0 : 1;
}

void show(char * str, int s, int n)
{
while(n-- > 0)
{
printf("%c", str[s++]);
}
printf("\n");
}

void show_max_sub_str(char * str)
{
int len = strlen(str);
int test = len / 2;
while(test)
{
int j;
for (j = 0; j + 2 * test <= len; ++j)
{
if (check(str, j, test))
{
show(str, j, test);
return;
}
}

test--;
}
}

int main(int argc, char * argv[])
{
if (argc > 1)
{
show_max_sub_str(argv[1]);
}

return 0;
}


参考：http://topic.csdn.net/t/20060608/13/4809010.html

---------------------------------------------------------------------------

给定一个关键字表，在一个文本里查找这些关键字。

思路：把关键字表建成树形，遍历文本，每一个字符建立一个指向关键字表树节点的指针，一个字符一个字符遍历下去，如果符合关键字的话，指针将在树上不断向下移动，如果可以移到叶子，说明找到一个关键字，输出，如果没找到叶子就出现不符合的现象，说明查找失败，将该指针删除，这样整篇文本遍历之后，关键字也都可以输出了。


参考：《一个人北漂的日子：北京求职90天纪实》
(http://www.it.com.cn/f/edu/0611/9/347299_1.htm)

---------------------------------------------------------------------------