字符串之子串

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