字符串专题1. 题目：输入一个字符串，要求找出字符串中最大子串的长度(如字符串abcd13agbf，当重复出现某个字符时，算一个子串，比如abcd13a或bcd13agb都是子串)。
理解：要是每个字符都不一样，则最大子串长度为0
思想：用空间换取时间，用一个数组lastPos[256]代表着256个可能的字符（ASC2码），而数组的值代表字符串中这个字符的最后出现位置，初始数组元素都为负数，然后每次取字符串中的一个字符，此字符的ASC2码为c，若lastPos[c]=0,则表示此字符已经出现过，则可以计算这个子串的长度，...
1. 题目：输入一个字符串，要求找出字符串中最大子串的长度(如字符串abcd13agbf，当重复出现某个字符时，算一个子串，比如abcd13a或bcd13agb都是子串)。
理解：要是每个字符都不一样，则最大子串长度为0
思想：用空间换取时间，用一个数组lastPos[256]代表着256个可能的字符（ASC2码），而数组的值代表字符串中这个字符的最后出现位置，初始数组元素都为负数，然后每次取字符串中的一个字符，此字符的ASC2码为c，若lastPos[c]<0,则表示此字符第一次出现，置lastPos[c]为此字符在字符串中的位置，若lastPos[c]>=0,则表示此字符已经出现过，则可以计算这个子串的长度，若比之前的最大子串长，则更新最大子串长度。
分析：时间复杂度为o（n）
int GetMaxSubStr(const unsigned char *str)
{
int maxLen = 0;
if (NULL == str)
return 0;
int lastPos[256]; //代表着256个可能的字符（ASC2码），数组元素值代表字符串中字符的最后出现的位置
for (int i = 0; i < 256; ++i)
lastPos[i] = -1;
for (int pos = 0; str[pos] != '\0'; ++pos)
{
unsigned char c = str[pos];
if (lastPos[c] > -1) //此字符已经出现过
{
int len = pos - lastPos[c] + 1; //计算子串的长度
if (len > maxLen)
maxLen = len;
}
lastPos[c] = pos;
}
return maxLen;
}
2. 找出两个字符串中的最长相同子串
算法的思想：利用二维数组建立两个字串之间的“对应矩阵”，然后初始化矩阵（mat[i][j]置1或0），然后根据矩阵的对角线找出连续出现1的最长段，及在串中的起始位置。
3. 在一个字符串中查找可能的最长子串，该子串由相同字符组成
#include
#include
void find(char* str, char*& start, int& length)
{
char* p = str;
char* q;
int len = 0;
length=0;
while(*p)
{
q = p+1;
while(*q && *q == *p)
q++;
len = q - p;
if(len>length)
{
length = len;
start = p;
}
p=q;
}
}
int main()
{
char str[1024];
scanf("%s", str);
char* p;
int len;
find(str,p, len);
p[len]=0;
printf("%s\n", p);
return 0;
}
4. 给定一个字符串,要求找出重复出现且最长的子串
5. Memcpy和memmove .
1)当 src 和 dest 所指内存区有重叠时，memmove 相对 memcpy 能提供保证：保证能将 src 所指内存区的前 n 个字节正确的拷贝到 dest 所指内存中；
2). 当 src 地址比 dest 地址低时，两者结果一样。换句话说，memmove 与 memcpy 的区别仅仅体现在 dest 的头部和 src 的尾部有重叠的情况下；
memcpy
代码:
void* memcpy(void* dest, void* source, size_t count)
{
void* ret = dest;
//copy from lower address to higher address
while (count--)
*dest++ = *source;
return ret;
}
memmove
void* memmove(void* dest, void* source, size_t count)
{
void* ret = dest;
if (dest <= source || dest >= (source + count))
{
//Non-Overlapping Buffers
//copy from lower addresses to higher addresses
while (count --)
*dest++ = *source++;
}
else
{
//Overlapping Buffers
//copy from higher addresses to lower addresses
dest += count - 1;
source += count - 1;
while (count--)
*dest-- = *source--;l
}
return ret;
}
本文档为【字符串专题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483