NAME \ N=   10000   20000    30000   40000   50000
----------------------------------------------------
crystalx     1121    5047    11146   22402   TimeOut
hucheng      1542    6769    14851   26247   TimeOut
poorb        1331    5758    13299   24975   TimeOut
redbullivws  1261    5217    12217   22272   TimeOut
yxs0001         0       0        0       0      10
雨中飞燕     1472    5718    12497   22422   TimeOut

不是一般的快啊

一不小心,成大错误!
少写了两个符号,出大糗了!
原:
for (int i=1; i<MAX; )
    {
        if (flag)//若出现重复字符串，则需要修改数组a的栈顶元素
            [color=FF0000]Change(a, i);[/color]        
        flag = false;    //重新赋值表示没有重复
        k = rand()%2 + 1; 
        Create(a, i, a[i-1][k]);//从a[i-1][1]和a[i-1][2]随机选取一个值作为a[i][0]的值 
        if (Cover(a, ++i))//如果出现连续重复部分则选取另外一个子串 
        {
            Create(a, i-1, a[i-2][3-k]);//若k==1，则3-k==2 ；若k==2，则3-k==1 
            if (Cover(a, i))//如果两个子串都不可取（出现连续重复），则数组长度减1，修改前一个子串 
            {
                --i;
                flag = true;
            }
        }
    }

红色部分改成[color=FF00FF]Change(a, i--);[/color]即可

请楼主再帮忙测试一次

goal00001111:
你的代码我测试了，能出结果的没有问题。

但是很怪， MAX为1561，N为4680时，结果一闪即现， 但MAX为1571，N为4710时，等了十几秒都不出来。。。  不知道为什么 ？
可能和测试的机器有关， 下午换机器试下。

下面是我的测试程序 （你自己也测一下，换个大点的数看能不能出结果）
#define N 4680
int main()
{
    char *p = (char *)malloc(N+10);
    
    unoverlap(N, p);
    
    printf("%d\n", test_str(p,N));
    //printf("%s",p);
    free(p);
    return 0;
}

还有就是没看你的main(), 所以以为要加p[0]=0;
其实你已经在main()将p初始化了。 不好意思

换了台机器， 是同一个数。

唯一的解释那就是不能完全由长度为3的子串组成。你的程序陷入了死循环。
到了一定长度以后必须由更短的长度，否则组成不了。如12 13

/*昨天测试了一下，发现我的程序并没出现向楼主所说的出现溢出，虽然我用的是递归回溯法！然后顺便找了几个进入第二次测评的代码，测了几个数据，发现时间上并比其他的差！也叫楼主帮忙测试了一下，他那边还是有错。(他用的是VC2005），我后来又把vc6.0改为了Dev-c++还是没有问题，并且时间上也都不差于其他几个。所以一直很纳闷为什么不同的编译器会出现这么大的差距。有谁帮忙测试一下。
下面是测试代码,要注意  MAX   N 的值！
你只要复制这段代码，在主程序中修改要循环的次数 
下面这是我在某次中测试大 数据！
把MAX改为30000，N改为20000，编译器改为了
Dev-c++4.9.9.2

循环 50次！
OK!!!
OK!!!
OK!!!  
OK!!!
 unoverlap1(N,p)    time = 123    //我的程序
 unoverlap1(N,p)    time = 185    
 unoverlap1(N,p)    time = 123
 unoverlap1(N,p)    time = 153

我不知道为什么我们测的会出现这样不同的结果,
也许你可以尝试一下其他编译器！！
很抱歉，我并不是证明什么，我只是想把问题搞明白。如果有什么打扰之处，请多多包涵！！！

 


*/

#include<time.h>
#include<iostream>
using namespace std;

#define MAX 30000          //最大的空间N<MAX
#define N  20000           //要生成的个数即 n；

///////////////////////////////////////////////////////////
               /*测试代码 用于判定生成的结果是否正确*/


//判断一个序列是否有连续重复的部分(以第n个字母结束的子串)
int overlap(const char *p, int n)
{
    int max = (n+1)/2;//如果有重复部分,则此长度是最大重复长度
    int length = 1;
    int end1, end2;//两个要比较的子串结尾

    for (; length<=max; length++)
    {
        for (end1=n,end2=n-length; end1>n-length && p[end1]==p[end2]; end1--,end2--)
            ;//比较两个子串
        if (end1 == n-length)//两子串相同,表明有重复
        {
            printf("\nlength:%d\n",length);
            return 1;
        }
    }

    return 0;
}


//判断一个字符序列里是否有重复的部分 1为不满足条件
int test_str(const char *p, int n)
{    
    int i = 2;

    for (; i<n; i++)
    {
        if (overlap(p,i) == 1)
        {
            printf("\nWhich:%d\n", i);
            return 1;
        }
    }

    return 0;
}
////////////////////////////////////////////////

/*    我的代码      */

bool Insert(char *p,int *mark,int cur,int n)
{
    bool Fit;
    int half=cur/2;                 //只要比对当前长度的一半就可以了
    int dist;   
    int i,j,last;
    char ch;                       //要存放的字符
    
/////////////////////////////////////////
   for(int k=0;k<3;k++)
   {
       if(cur==n)
           return true;

       Fit=true;                        //用于表示当前值是否符合
       ch='1'+k;
       last=cur-1;

      while(last>=0&&p[last]!=ch)last--;  //找到最近的前一个与当前值一样的下标
      
      for(i=last;i>=half && Fit;i=mark[i])
      {
           dist=cur-i;                         //当前值与某个相同下标的距离
           j=cur-1;

           while(j>i && p[j-dist]==p[j])j--;    //逐个匹配

           if(j<=i) Fit=false;                 //判断是否符合

      }
         if(Fit)
         {
            p[cur]=ch;
            mark[cur]=last;
        
            if(Insert(p,mark,cur+1,n))   //不满足则回溯
                return true;
            
         }
   }

    return false;
}

void unoverlap1(int n, char *p)    //函数接口
{
   if(n>=MAX || n<0)         
       return ;

   int *mark = new int[MAX];      //用于标记与当前值对应的前一个值，相当于指针
   memset(mark,-1,MAX);
   
   Insert(p,mark,0,n);           

 
   delete []mark;

}




/*     作者：poorb          */

int Is_oK(char *base,int top)
{
     int p;
     int k;
     int foot;

     if(base[top-1] == base[top])
        return 0;

     k = (top+1)/2;

     for(foot = 2; foot <= k; foot++)
     {

         for(p = 0 ; p < foot && base[top-p] == base[top-foot-p];p++);
         if(p >= foot)
         return 0;
     }
     return 1;
}
void unoverlap2(int n, char *p)
{
    int now = 1;
    p[0] = '1';

    while(now < n)
    {
        p[now] = '1';

        while(!Is_oK(p,now))
        {
             for(;p[now] == '3';now--);
                p[now]++;
        }
        now++;
    }

    //printf("%s",p);
}

///////////////////////////          作者：crystalx  ////////////////
bool check(int end,char *p)
{
    for(int i = 1; i <= (end + 1)/2; i++ )
    {
        int j = 0;
        for( ; j < i; j++ )
            if (p[end - j] != p[end - j - i]) break;
        if(j >= i) return false;
    }
    return true;
}
void unoverlap3(int n, char *p)
{
    for(int i = 0; i < n; i++)
    {
        p[i] ++ ;
        while( p[i] <= '3' )
        {
            if(check(i,p)) break;  //可以放这个数字
            p[i]++;
        }
        if(p[i] > '3')   //回溯
        {
            p[i] = '0';
            i = i - 2;
        }
    }
}
 


///////作者：雨中飞燕/////////////

void unoverlap4(int n, char *p)
{
    p[0]='3';p[1]='2';p[2]='1';
    //p[3]='2';p[4]='1';p[5]='3';
    int n1, nt;
    for(n1=3,p[n1]='0',nt=1;n1<n;nt++)//current index
    {
        int n2=p[n1]+1,fnn=-1;
        for(;n2<='3';n2++)//current number
        {
            int bUse=1;
            fnn=-1;
            if(n2==p[n1-1])continue;
            for(int nm=(n1>>1),n3=n1-2,nn; n3>=nm; n3--) //compare
            {
                if(p[n3]==n2) //first char the same
                {
                    int n4=1,ne=n1-n3;
                    nn=-1;
                    if(fnn==-1)fnn=n3;
                    for(;n4<ne;n4++) //compare other chars
                    {
                        char c=p[n3-n4];
                        if(c==n2)
                        {
                            nn=n3-n4; //mark next first char
                            for(;n4<ne;n4++)
                            {
                                if(p[n3-n4]!=p[n1-n4])break; //if not same then break
                            }
                            break;
                        }
                        if(p[n3-n4]!=p[n1-n4])break;
                    }
                    if(n4>=ne) //the same
                    {
                        bUse=0;
                        break;
                    }
                    else //seach next
                    {
                        if(nn>=0)n3=nn;
                    }
                }
            }
            if(bUse==1) //no the same
            {
                break;
            }
        }
        if(n2<='3') //goto next char
        {
            p[n1++] = n2;
            p[n1]='0';
        }
        else //go back
        {
            p[n1--]='0';
            //nRedo++;
        }
    }
    p[n]=0;
}

int main(void)
{
    char *p=new char[MAX];
    
    time_t startTime;
    time_t endTime1,endTime2,endTime3,endTime4;

   

    time(&startTime);

///////////////////////////
    for(int i=0;i<50;i++)
    {
    unoverlap1(N,p);
    }
    
        
    if(test_str(p,N))
    {
        cout<<"error!!!";
    }
    cout<<"OK!!!"<<endl;
    time(&endTime1);

///////////////////////

   for(int i=0;i<50;i++)
    {
    unoverlap2(N,p);
    }
    
        
    if(test_str(p,N))
    {
        cout<<"error!!!";
    }
    cout<<"OK!!!"<<endl;
    time(&endTime2);
   
////////////////////////

for(int i=0;i<50;i++)
    {
    unoverlap1(N,p);
    }
    
        
    if(test_str(p,N))
    {
        cout<<"error!!!";
    }
    cout<<"OK!!!"<<endl;
    time(&endTime3);   
    
//////////////////////   

for(int i=0;i<50;i++)
    {
    unoverlap4(N,p);
    }
    
        
    if(test_str(p,N))
    {
        cout<<"error!!!";
    }
    cout<<"OK!!!"<<endl;
    time(&endTime4); 
//////////////////////////
    
    
    
    
    
    
    cout << "unoverlap1(N,p)    time = " << difftime(endTime1, startTime) << endl;
    
    cout << "unoverlap2(N,p)    time = " << difftime(endTime2, endTime1) << endl;
    
    cout << "unoverlap3(N,p)    time = " << difftime(endTime3, endTime2) << endl;
    
    cout << "unoverlap4(N,p)    time = " << difftime(endTime4, endTime3) << endl;
    system("pause");
    return 0;
}

//我改过之后的，比原来快了点。主要是check()的效太低了。我的测试代码是用的是check4()。
void unoverlap(int n, char *p)
{
    char *q = p;
    
    *q = '0';
    while (q - p < n)
    {
        if (++*q > '3')
        {
            q--;
            continue;
        }

        if (!check4(p, q))
        {
            *++q = '0';
        }
    }
    *q = '\0';
}



int check4(char *p, char *top)
{
    char *left = top;
    char *leftTmp, *rightTmp;
    
    if (p == top)
        return 0;
    do{
        while ((--left >= p) && (*left != *top))
            NULL;
        for (leftTmp=left, rightTmp=top;
        (--rightTmp > left) && (*--leftTmp == *rightTmp); )
            NULL;
        if (rightTmp == left--)    //有重复出现
            return 1;
    }while ((left + left - p + 1) >= top);
    return 0;    //OK, 无重复
}