---------------------------------------------------------------------------
给定一个字符串,求其最长连续重复子串,如果有多个则返回第一个。例如 “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)
---------------------------------------------------------------------------
分享到:
相关推荐
总结的一些笔试过程中的C语言练习题,虽然不会再出现原题但是可以学习学习其中的思想。万变不离其宗。资源主要是关系笔试部分的字符串专项练习。
1) 院士奖学金,每人8000元,期末平均成绩高于80分(>80),并且在本学期内发表1篇或1篇以上论文的学生均可获得; 2) 五四奖学金,每人4000元,期末平均成绩高于85分(>85),并且班级评议成绩高于80分(>80)的学生...
自己整理的校招笔试面试时,主要的字符串题型。
acm习题,字符串处理 ,必做题解析,题目经典,含有解析
通过键盘输入一串小写字母(a~z)组成的字符串,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串。 压缩字段的格式为"字符重复的次数+字符"。例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。 要求实现...
1 将字符串转化为整数。2 将整数转化为字符串(考虑正负号的问题)。3 实现字符串拷贝函数strcpy(程序的完整性)。4 编程实现memcpy函数(以字节为单位的拷贝)。5 编程实现memmove函数。 等笔试题。
一些与字符串有关的常考的面试题,用C语言实现的
自己总结的面试常见题 C++字符串处理 自己总结的面试常见题 C++字符串处理
1.字符串高频面试题精讲1.字符串高频面试题精讲1.字符串高频面试题精讲
传入一个字符串和整数m,将此字符串中从第m个字符开始的全部字符复制成为另一个字符串并打印出来。
输入一个字符串,将输出该字符串最长对称子串及其长度,很精巧的算法
字符串相关笔试题 面试时常考,很不错的说
字符串计数 C语言实现 ACM习题
iOS 开发的oc编程语言中字符串练习题.doc
输入一个字符串,统计出这个字符串的英文大写字母、小写字母、数字、空格以及其它字符的个数
功能是把定长字符串映射为整数,目的是找到比用C++标准库无序映射unordered_map更快的算法。所有字符串的长度都一样,且初始化之后只有查询,没有增删改。不同功能字符串长度也不同,但不超过16。本程序随机生成长度...
VB字符串处理详解
这东西对基础不扎实的同学最好,对基础好的同学也挺好的
输入一个字符串t和一个正整数m,将字符串t中从第m个字符开始的全部字符复制到字符串s中,再输出字符串s。要求用字符指针定义并调用函数strmcpy(s,t,m),它的功能是将字符串t中从第m个字符开始的全部字符复制到字符串...
关于结束符'\0'能否影响free()的使用,觉得是完全不用操心的,因为malloc的大小是系统来保存的,删除时候系统来接手就完了,而'\0'结束符只是针对一些常规字符串操作,比如printf()用%s控制输出时~! 新难点:...