字符串相关问题（二）

【问题一】
    删除字符串中的数字并压缩字符串。如字符串“abc123de4fg56”处理后变为“abcdefg”。注意空间和效率。
解答：
    设置两个指着pfast和plast，pfast进行遍历，如果遇到数字，则pfast++；反之，把pfast所指向的字符赋值给plast，然后二者均向前走一步。
    该方法只需要遍历一次，不需要开辟新的空间，时间复杂度为O(n)。

//压缩字符串
void Squasd(char *str)
{
    assert((str != NULL));

    char *pfast = str;
    char *plast = str;

    while(*pfast != '\0')
    {
        if(*pfast <= '9' && *pfast >= '0')
        {
            pfast++;
        }
        else
        {
            *plast = *pfast;
            plast++;
            pfast++;
        }
    }
    *plast = '\0';
}

【问题二】
    编写一个函数，将字符串中的字符‘*’移动到串的前部分，前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中的字符‘*’的数量。
    如原始串为：ab**cd**e*12，处理后为****abcde12，函数并返回值为5。要求尽量使用少的时间和辅助空间。
解答：
    设置两个指针，从后往前，进行扫描，时间复杂度为O(n)。

//将字符串中的字符'*'移到串的前部分，前面的非'*'字符后移
void Swap(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}
void Remove(char *str)
{
    assert((str != NULL));
    int length = strlen(str);
    char *pfast = str + length - 1;
    char *plast = str + strlen(str) - 1;

    while(pfast != str && plast != str)
    {
        //从后向前找到第一个*
        while(*pfast != '*' && pfast != str)
        {
            pfast--;
        }

        //从该*开始，向前找到第一个非*
        plast = pfast;
        while(*plast == '*' && plast != str)
        {
            plast--;
        }
        Swap(&(*plast), &(*pfast));
        pfast--;
    }
}

【问题三】
    求最大连续递增数字串。如“ads3sl456789DF3456ld345AA”中的“456789”。
解答：

#define MAX 100
void FindMaxLong(char *str)
{
    if(str == NULL)
    {
        return;
    }

    int max = 0;            //记录最大长度
    int last = -1;            //记录上一个字符
    int endindex = 0;        //记录最长递增数字串的开始位置
    int len = strlen(str);

    int result[MAX];
    result[0] = 0;

    int i = 0;
    for(i = 0; i < len; i++)
    {
        if( (str[i] >= '0' && str[i] <= '9') && (str[i] - '0' > last) )
        {
            last = str[i] - '0';
            //注意这里开始时：result[i] = result[i - 1] + 1;
            //当字符串第一个字符为数字时，会出现：result[0] = result[-1] + 1;
            //所以修改为如下。
            result[i + 1] = result[i] + 1;
            if(result[i + 1] > max)
            {
                max = result[i + 1];
                endindex = i;
            }
        }
        else
        {
            last = -1;
            result[i] = 0;
        }
    }

    printf("最长递增数字串长度为：%dn", max);
    printf("最长递增数字串为：n");
    for(i = endindex - max + 1; i <= endindex; i++)
    {
        printf("%c ", str[i]);
    }
    printf("n");
}

【附加题】
    找到一个字符串中的一个连续子串，这个子串不能有任何两个字符是相同的，并且这个子串是符合要求的最长的。
    例如，输入“abcbef”，输出“cbef”。
解法：
    时间复杂度为O(n)的算法，具体思路如下所示：
    以"abcbef"这个串为例子，用一个数组pos记录每个元素曾出现的下标，初始化为-1。从str[0]开始，依次考察每个字符，例如pos['a'] == 0，说明‘a'还没有出现过，令pos['a'] = 0，视为将’a'加入到当前串中，同时长度加+1，同理pos['b'] = 1，pos['c'] = 2，考察str[3]，pos['b'] != -1，说明‘b'在前面已经出现过了，此时可得到一个不重复串“abc”，刷新当前的最大长度，然后更新pos['b']以及起始串位置。
    具体过程如下：
    （1）建立一个256个单元的数组，每一个单元代表一个字符，数组中保存上次该字符出现的位置；
    （2）依次读入字符串，同时维护数组的值；
    （3）如果遇到冲突的，考察当前起始串位置到冲突字符的长度，如果大于当前最大长度，则更新当前最大长度并维护冲突字符的位置，更新起始串的位置，继续第二步；

//最长不重复的连续子串
char* GetMaxSubStr(char *str)
{
    int i = 0;

    //hash记录每个字符的出现位置
    int hash[256];
    //初始化
    for (i = 0; i < 256; i++)
    {
        hash[i] = -1;
    }

    int CurrentStart = 0, CurrentLength = 0;
    int MaxStart = 0, MaxEnd = 0;

    int strLen = strlen(str);

    for(i = 0; i < strLen; i++)
    {
        int index = str[i];
        if(CurrentStart > hash[index])            //如果没有重复
        {
            hash[index] = i;
        }
        else
        {
            CurrentLength = i - CurrentStart; //当前长度
            if(CurrentLength > MaxEnd-MaxStart)//如果当前长度最长
            {
                MaxEnd = i;
                MaxStart = CurrentStart;
            }
            CurrentStart = hash[index] + 1; //更新当前最长的起点
            hash[index] = i;                 //更新字符出现的位置
        }
    }
    if (MaxEnd == 0)                         //没有重复字符，返回源串
    {
        char* reStr = new char[strLen + 1];
        strcpy(reStr, str);
        return reStr;
    }

    CurrentLength = strLen - CurrentStart; //当前长度
    if(CurrentLength > MaxEnd - MaxStart) //如果当前长度最长
    {
        MaxEnd = strLen;
        MaxStart = CurrentStart;
    }
    //获取最大长度和最大连续不重复子串
    int MaxLength = MaxEnd - MaxStart;
    printf("长度为: %dn", MaxLength);
    char* reStr = new char[MaxLength + 1];
    memset(reStr, 0, MaxLength + 1);
    strncpy(reStr, str + MaxStart, MaxLength);
    return reStr;
}

【问题五】
    已知一个字符串，比如“aderwsde”，寻找其中一个子字符串比如“sde”的个数。如果没有找到，则返回0；否则返回该子字符串的个数。
解答：
    利用strstr()或KMP算法进行匹配。

【问题六】
    给出一个函数来复制两个字符串 A 和 B。字符串 A 的后几个字节和字符串 B 的前几个字节重叠。
解答：
    分析：记住，这种题目往往就是考你对边界的考虑情况。
    具体思路没有想到。

【问题七】
    对称字符串的最大长度。
    输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
解答：
    参考：http://www.cnblogs.com/wolenski/archive/2012/07/08/2581837.html
    分析：可能很多人都写过判断一个字符串是不是对策的函数，这个题目可以看成是该函数的加强版。
  
引子：判断字符串是否对称
    要判断一个字符串是不是对称的，不是一件很难的事情。我们可以先得到字符串的首尾两个字符，判断是不是相等。如果不相等，那么该字符串肯定不是对称的；否则继续判断里面的两个字符是不是相等。基于这个思路，写出如下代码：

////////////////////////////////////////////////////////////////
 // Whether a string between pBegin and pEnd is symmetrical?
 ////////////////////////////////////////////////////////////////
 bool IsSymmetrical(char* pBegin, char* pEnd)
 {
        if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
               return false;

        while(pBegin < pEnd)
        {
               if(*pBegin != *pEnd)
                      return false;

               pBegin++;
               pEnd --;
        }

        return true;
 }

    要判断一个字符串pstring是不是对策的，我们只需要调用IsSymmetrical(pstring, &pstring[strlen(pstring) - 1])就可以了。
解法一：O(n^3)的算法
    现在我们试着得到对称字符串的最大长度。最直观的做法就是得到输入字符串的所有子字符串，并逐个判断是不是对策的。如果一个字符串是对称的，我们就得到它的长度。这样经过比较，就能得到最长的对称子字符串的长度了。于是，可以写出如下代码：

////////////////////////////////////////////////////////////////
 // Get the longest length of its all symmetrical substrings
 // Time needed is O(T^3)
 ////////////////////////////////////////////////////////////////
 int GetLongestSymmetricalLength_1(char* pString)
 {
        if(pString == NULL)
               return 0;

        int symmeticalLength = 1;

        char* pFirst = pString;
        int length = strlen(pString);
        while(pFirst < &pString[length - 1])
        {
               char* pLast = pFirst + 1;
               while(pLast <= &pString[length - 1])
               {
                      if(IsSymmetrical(pFirst, pLast))
                      {
                            int newLength = pLast - pFirst + 1;
                            if(newLength > symmeticalLength)
                                   symmeticalLength = newLength;
                      }

                      pLast++;
               }

               pFirst++;
        }

        return symmeticalLength;
 }

    我们来分析一下上述方法的时间效率。由于我们需要两重while循环，每重循环需要O（n）的时间。另外，我们在循环中调用了IsSymmetrical，每次调用也需要O（n）的时间。因此整个函数的时间效率是O（n^3）。
    通常O（n^3）不会是一个高效的算法。如果我们仔细分析上述方法的比较过程，我们就能发现其中有很多重复的比较。假设我们需要判断一个子字符串具有aAa的形式（A是aAa的子字符串，可能含有多个字符）。我们先把pFirst指向最前面的字符a，把pLast指向最后面的字符a，由于两个字符相同，我们在IsSymtical函数内部向后移动pFirst，向前移动pLast，以判断A是不是对称的。接下来若干步骤之后，由于A也是输入字符串的一个子字符串，我们需要再一次判断它是不是对称的。也就是说，我们重复多次地在判断A是不是对称的。
    造成上述重复比较的根源在于IsSymmetrical的比较是从外向里进行的。在判断aAa是不是对称的时候，我们不知道A是不是对称的，因此需要花费O（n）的时间来判断。下次我们判断A是不是对称的时候，我们仍然需要O（n）的时间。

解法二：O(n^2)的算法
    如果换一种思路，我们从里向外来判断。也就是先判断字符串A是不是对称的。如果A不是对称的，那么该子字符串两端各延长一个字符得到字符串肯定不是对称的。如果A对称，那么只需要判断A两端延长的一个字符是不是相等，如果相等，则延长后的字符串是对称的。因此在知道A是否对称之后，只需要O(1)的时间就知道aAa是不是对称的。
    可以根据从里向外的思路写出如下代码。

////////////////////////////////////////////////////////////////
 // Get the longest length of its all symmetrical substrings
 // Time needed is O(T^2)
 ////////////////////////////////////////////////////////////////
 int GetLongestSymmetricalLength_2(char* pString)
 {
        if(pString == NULL)
               return 0;

        int symmeticalLength = 1;

        char* pChar = pString;
        while(*pChar != '')
        {
               // Substrings with odd length
               char* pFirst = pChar - 1;
               char* pLast = pChar + 1;
               while(pFirst >= pString && *pLast != '' && *pFirst == *pLast)
               {
                      pFirst--;
                      pLast++;
               }

               int newLength = pLast - pFirst - 1;
               if(newLength > symmeticalLength)
                      symmeticalLength = newLength;

               // Substrings with even length
               pFirst = pChar;
               pLast = pChar + 1;
               while(pFirst >= pString && *pLast != '' && *pFirst == *pLast)
               {
                      pFirst--;
                      pLast++;
               }

               newLength = pLast - pFirst - 1;
               if(newLength > symmeticalLength)
                      symmeticalLength = newLength;

               pChar++;
        }

        return symmeticalLength;
 }

    回帖中指出了原文的问题：
    当char *pChar =pString
           char* pFirst = pChar - 1;时，pFirst指向一个未知区域了，那后面的int newLength = pLast - pFirst - 1;是不是有问题！
    循环可以不用在pChar = pString处开始，而在pChar = pString + 1处开始，那么奇数长度的代码不变，偶数长度的代码改一下就行了：
           pFirst = pChar - 1;
           pLast = pChar ;
    由于子字符串的长度可能是奇数也可能是偶数。长度是奇数的字符串是从只有一个字符的中心向两端延长出来，而长度为偶数的字符串是从一个有两个字符的中心向两端延长出来。因此我们的代码要把这种情况都考虑进去。
    在上述代码中，我们从字符串的每个字符串两端开始延长，如果当前的子字符串是对称的，再判断延长之后的字符串是不是对称的。由于总共有O（n）个字符，每个字符可能延长O（n）次，每次延长时只需要O（1）就能判断出是不是对称的，因此整个函数的时间效率是O（n2）。