一、找出字符串的最长子串
1、原理
找出字符串的最长子串，要求子串的所有字符相同，比如：字符串strSource="abcccdeeeeffg"，则子串strSubstring="eeee"。
记录下原子串的初始起始位置和长度，遍历整个字符串，依次比较当前字符与子串字符是否相同，相同则子串长度加1，不同则比较当前子串与原最长子串的长度，保留最长子串长度和位置到原子串信息中，重新开统计当前子串，直到遍历完整个字符串。
2、实现
#include
#include
char* GetSubstring(char* strSource)
{
if (NULL == strSource)
{
return NULL;
}
char *strSubstring = NULL; //用于保存得到的子串，大小在找到最大子串后再确定，作为返回值
int nLen = strlen(strSource); //源字符串长度
int nCurPos = 0; //当前统计字符串的头指针位置(相对于原字符串第一个字符的位置)
int nCurCount = 1; //当前统计字符串的长度（有相同字符组成的子字符串）
int nPos = 0; //当前最长的子串的头指针位置
int nCount = 1; //当前最长的子串的长度
//遍历整个字符串
for (int i=1; i
{
if (strSource[i] == strSource[nCurPos]) //如果当前字符与子串的字符相同，子串长度增1
{
++nCurCount;
}
else //如果不相同，开始统计新的子串
{
if (nCurCount > nCount) //如果当前子串比原先最长的子串长，把当前子串信息(起始位置 + 长度)保留下来
{
nCount = nCurCount;
nPos = nCurPos;
}
//长度赋值为1，新子串的开始位置为i
nCurCount = 1;
nCurPos = i;
}
}
//为返回的子串分配空间(长度为nCount,由于要包括字符串结束符\0,故大小要加1)
strSubstring = new char[nCount + 1];
//复制最长子串
for (int i=0; i
{
strSubstring[i] = strSource[nPos + i];
}
strSubstring[nCount] = '\0';
return strSubstring;
}
int main()
{
//输入一个字符串strSource
char *strSource="abcccdeeeeffg";
char *strSubstring = GetSubstring(strSource);
printf("Source: %s\nThe max substring: %s\n", strSource, strSubstring);
//释放strSubstring
delete [] strSubstring;
return 0;
}
二、找出字符串中连续出现次数最多的子串
1、原理
找出字符串中连续出现次数最多的子串，要求子串连续出现，比如：字符串strSource="abcbcbcabcabdabab"，则出现连续次数最多的子串strSubstring="bc"。
记录下原子串的初始起始位置和长度，遍历整个字符串，依次比较当前字符与子串字符是否相同，相同则子串长度加1，不同则比较当前子串与原最长子串的长度，保留最长子串长度和位置到原子串信息中，重新开统计当前子串，直到遍历完整个字符串。
2、实现
#include
#include
using namespace std;
char* find_str(char *strSource, int &iCount)
{
if (NULL == strSource)
{
return NULL;
}
int len = strlen(strSource);
int tmpcnt = 0;
char *strSubstring = new char[len+1];
memset(strSubstring, 0, len+1);
for (int i=0; i
{
for (int j=i+1; j
{
int n = j-i; //子串长度
tmpcnt = 1;
if (0 == strncmp(&strSource[i], &strSource[j], n)) //比较n长度子串
{
++tmpcnt; //相等则累加计数器
for (int k=j+n; k
{
if (0 == strncmp(&strSource[i], &strSource[k], n))
{
tmpcnt++;
}
else
{
break;
}
}
if (iCount < tmpcnt)
{
iCount = tmpcnt; //保存计数器
memset(strSubstring, 0, len+1); //清空上次保存的子串
memmove(strSubstring, &strSource[i], n); //保存子串
}
}
}
}
return strSubstring;
}
int main()
{
char *strSource = "abcbcbcabcabdabab";
char *strSubstring = NULL;
int iCount = 0;
strSubstring = find_str(strSource, iCount);
printf("Source=%s\nSubstring=%s\nCount=%d\n", strSource, strSubstring, iCount);
return 0;
}
三、两字符串的最大公共子字符串
1、原理
从两个字符串中挑选出其中一个字符串，从该字符串的第一个字符开始，依次与第二个字符串的各个字符比较，并更新最长公共子串的位置和长度，直至第一个字符串遍历结束。
2、实现
#include
#include
using namespace std;
char* FindMaxSubstr(const char *str1 , const char *str2 , char *maxsubstr)
{
if ((NULL == str1) || (NULL == str2) || (NULL == maxsubstr))
{
return NULL;
}
int maxpos = -1; //最长公共子串在str1中的位置
int maxlen = 0; //最长公共子串在str1中的长度
int k = 0;
for (unsigned int i=0; i
{
for (unsigned int j=0; j
{
if (str1[i] == str2[j])
{
//计算最大公共子串长度
for (k=1; (str1[i+k]==str2[j+k])&&(str1[i+k]!='\0'); k++)
{
;
}
// 更新最大公共子串位置和长度
if (k > maxlen)
{
maxpos = i;
maxlen = k;
}
}
}
}
if (maxpos == -1)
{
maxsubstr[0]='\0';
}
else
{
memmove(maxsubstr, str1+maxpos, maxlen);
maxsubstr[maxlen] = '\0';
}
return maxsubstr;
}
int main()
{
char maxsubstr[20] = {0};
char str1[] = "helloshichangquan";
char str2[] = "worldshichangquan";
FindMaxSubstr(str1, str2, maxsubstr);
printf("str1=%s\nstr2=%s\nmaxsubstr=%s\n", str1, str2, maxsubstr);
return 0;
}
四、第二个字符串在第一个字符串中第一次出现的位置
1、原理
比如：str1="changquanshihelloshi"，str2="shi"，那么str2在str1中第一次出现的位置在9（下标从0开始算起）。
从第二个字符串的第一个字符开始，依次与第一个字符串的各个字符比较，如果一直到第二个字符串结尾都相等，则找到第一次出现的位置了，否则从第一个字符串的位置加1起重新开始查找匹配，如此这般，直到找到位置或者第一个字符串到达结尾则结束查找。
2、实现
#include
char *strstr(char *str1, char *str2)
{
if (NULL == str1)
{
return NULL;
}
if (NULL == str2)
{
return str1;
}
char *base = str1;
char *sub = str2;
while (*base)
{
base = str1;
sub = str2;
do
{
if (*sub == '\0')
{
return str1;
}
} while (*base++ == *sub++);
str1 += 1; //从下一个位置重新开始查找
}
return NULL;
}
int main()
{
char str1[] = "changquanshihelloshi";
char str2[] = "shi";
printf("str1=%s\nstr2=%s\npos=%s\n", str1, str2, strstr(str1, str2));
return 0;
}
五、第二个字符串在第一个字符串中出现的总次数
1、原理
比如：str1="changquanshihelloshi"，str2="shi"，那么str2在str1中总共出现2次。
从第二个字符串的第一个字符开始，依次与第一个字符串的各个字符比较，如果一直到第二个字符串结尾都相等，则累加一次计数器，否则从第一个字符串的位置加1起重新开始查找匹配，如此这般，直到第一个字符串到达结尾则结束统计。
2、实现
#include
int strstr(char *str1, char *str2)
{
if (NULL == str1)
{
return -1;
}
if (NULL == str2)
{
return 0;
}
char *base = str1;
char *sub = str2;
int count = 0;
int pos = 0;
while (*base)
{
base = str1;
sub = str2;
pos = 0;
do
{
++pos;
if (*sub == '\0')
{
++count;
break;
}
} while (*base++ == *sub++);
str1 += pos; //从下一个位置重新开始查找
}
return count;
}
int main()
{
char str1[] = "changquanshihelloshi";
char str2[] = "shi";
printf("str1=%s\nstr2=%s\ncount=%s\n", str1, str2, strstr(str1, str2));
return 0;
}
阅读(3581) | 评论(2) | 转发(2) |
