字符串反转

时间：2010-09-07 来源：wsnhyjj

我没有记错的话是一道MSN的笔试题，网上无意中看到的，拿来做了一下。题目是这样的，给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。例如：
输入：第一个字符串: "This is zhuxinquan's Chinese site: http://www.zhuxinquan.com/cn"
子串: "zhuxinquan"
输出： "nc/moc.zhuxinquan.www//:ptth :etis esenihC s'zhuxinquan si sihT"
一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将子串倒过来压入堆栈。
最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下：

#include <iostream>
#include <cassert>
#include <stack>
using namespace std;
//reverse the string 's1' except the substring 'token'.
const char* reverse(const char* s1, const char* token)
{
        assert(s1 && token);
        stack<char> stack1;
        const char* ptoken = token, *head = s1, *rear = s1;
        while (*head != '\0')
        {
                while(*head!= '\0' && *ptoken == *head)
                {
                        ptoken++;
                        head++;
                }
                if(*ptoken == '\0')//contain the token
                {
                        const char* p;
                        for(p=head-1;p>=rear;p--)
                                stack1.push(*p);

                        ptoken = token;
                        rear = head;
                }
                else
                {
                        stack1.push(*rear);
                        head=++rear;
                        ptoken = token;
                }
        }
        char * return_v = new char[strlen(s1)+1];
        int i=0;
        while(!stack1.empty())
        {
                return_v[i++] = stack1.top();
                stack1.pop();
        }
        return_v[i]='\0';
        return return_v;
}
int main(int argc, char* argv[])
{
        
        cout<<"This is zhuxinquan's Chinese site: http://www.zhuxinquan.com/cn\n";
        cout<<reverse("This is zhuxinquan's Chinese site: http://www.zhuxinquan.com/cn","zhuxinquan");
        return 0;
}

相关阅读更多 +