首页 > 数据结构与算法 > 字符串之子串
2016
10-10

字符串之子串

一、找出字符串的最长子串
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;
}

 

 转自:http://blog.chinaunix.net/uid-22312037-id-3691321.html

最后编辑:
作者:liujg
真实-不弄虚,不做假,做自己,不违心; 踏实-不浮躁,不盲从,不急功,不近利; 实学-不投机,不取巧,勤于学,精于业。