合并算法

admin1

// MergeTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <vector>
#include <list>
#include <string>
//#include <stdio>
#include <iosfwd>

#include <windows.h>

using namespace std;

bool IsEqual(const string& a,const string& b)
{
        int nlen = a.length();
        for (int i = 0; i < nlen; ++i)
        {
                int jjlen = b.length();
                for (int jj = 0; jj < jjlen; ++jj)
                {
                        if (a[i] != b[jj])
                        {
                                return false;
                        }
                }
        }
        return true;
}

int main()
{
        list<string> strList;
        for (int i = 0; i < 500; ++i)
        {
                strList.push_back("c");
                strList.push_back("a");
                strList.push_back("b");
                strList.push_back("a");
                strList.push_back("a");
                strList.push_back("b");
                strList.push_back("b");
                strList.push_back("c");
                strList.push_back("a");
                strList.push_back("d");
        }

        DWORD time_start, time_end;
        time_start = GetTickCount();

        auto curIt = strList.begin();
        for (; curIt != strList.end(); ++curIt)
        {
                while (true)
                {
                        bool added = false;
                        auto nextIt = curIt;
                        ++nextIt;
                        for (; nextIt != strList.end(); ++nextIt)
                        {
                                if (IsEqual(*curIt,*nextIt))
                                {
                                        (*curIt) += (*nextIt);
                                        strList.erase(nextIt);
                                        added = true;
                                        break;
                                }
                        }
                        if (added == false)break;
                }
        }

        time_end = GetTickCount();

        double runTime = (time_end - time_start) / 1000.0;

        return 0;
}