bool check_ok(int length,char* p)
{
    for(int i=1;i<=length/2;i++)
    {   
        bool temp = false;
        for(int j =0;j<i;j++)
        {
            if(*(p-i-j) != *(p-j))temp = true;
        }
        if(!temp) return false;//存在连续重复的串
    }
    return true;
}

void fstring(int* count,int n,char* p)
{            
    if(*count>n)
    {
        return;
    }
    else
    {
        for(int i =1;i<=3;i++)
        {
            *p='1'+i-1;
            if(check_ok(*count,p))
            {
                if(*count<=n)(*count)++;
                p++;
                fstring(count,n,p);
                p--;
                if(*count > n)break;
                else (*count)--;
            }
            if(*count > n)break;
        }
        return ;
    }
}


void unoverlap(int n, char* p)
{
    int count= 1;
    char* q =p;
    fstring(&count,n,p);
    while(n-->0)
    {
        cout<<*q;
        q++;        
    }
    cout<<endl;
}

//朴实的回朔

#include <iostream>
#include <cstring>

using namespace std;
typedef struct state{
    char data[2];
    int state;
}State;

void makenext(int i,char p,State next[]);
void unoverlap(int n, char *p);
int compare(char *,int);
char *substring(const char*,int,int);

int main(int argc, char *argv[])
{
   char *p=new char[1000];
   unoverlap(9,p);
    cout<<p<<endl;
    system("PAUSE");    
    return 0;
}
 

void unoverlap(int n, char *p){

    State next[n+1];
    int i=1;
    char *t;
    p[0]='1';
    makenext(0,p[0],next);
    if(n>0)
    {
        while(i<n&&i>=0){
            if(next[i].state<1){
                p[i]=next[i].data[++next[i].state];
                makenext(i,p[i],next);
            }
            else
            {i--;
                    continue;}
            p[i+1]='\0';
            if(compare(p,i+1)){
                makenext(i,p[i],next);
                i++;
            }
            
            else if(!compare(p,i+1)&&i>=0&&next[i].state<1){
                    p[i]=next[i].data[++next[i].state];
                    if(!compare(p,i+1))
                        i--;
                    else{
                        makenext(i,p[i],next);
                        i++;
                    }
            }
            else
                i--;
        }
    }
    else return;
    p[n]='\0';
}

int compare(char *p,int s){
    int n=((s%2==0)?(s/2):(s/2+1));
    int k=s-1;
    char *t;
    for(int i=k;i>=n;i--){
        t=substring(p,i-1-(k-i),i-1);
        if(strcmp(p+i,t)==0)
            return 0;
    }
    return 1;
}

char* substring(const char *p,int a,int b){
    char *r;
    r=new char[b-a+2];
    int i;
    for( i=0;i<=(b-a);i++)
        r[i]=p[a+i];
   r[i]='\0';
    return r;
}

void makenext(int i,char p,State next[]){
    if(p=='1'){
        next[i+1].data[0]='2';
        next[i+1].data[1]='3';
        next[i+1].state=-1;
    }
    else if(p=='2'){
        next[i+1].data[0]='1';
        next[i+1].data[1]='3';
        next[i+1].state=-1;
    }
    else{
        next[i+1].data[0]='1';
        next[i+1].data[1]='2';
        next[i+1].state=-1;
    }
}

汗死，这样的输出内容不确定，不好测试吧

偶的代码：
#include <stdio.h>
//int nRedo=0;
void unoverlap(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;
}

#include <string.h>
int main()
{
    int n;
    char c[100000];
    while(scanf("%d",&n) != EOF)
    {
        //nRedo=0;
        unoverlap(n,c);
        puts(c);
        //n=chk(strlen(c),c);
        //printf("%d,%d\n", n,nRedo);
    }
    return 0;
}

偶写的太垃圾了，不过也没心情再改下去了，想不到比n^2更快的

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
using namespace std;

const int DIGITS=12;

// void unoverlap(int DIGIT, char *p); // 接口(没使用)

int append_c(vector<string>&v1, vector<string>&v2);
bool str_check(const char* str, int strlen, int n);
void v_str_check(vector<string>&v, int size, int strlen, int n);


int main(){

      vector<string> va(0);
      vector<vector<string> > code_table(DIGITS+1,va);  ///

      int i, j;

//生成单字母的字串数组,作为基础
code_table[0].push_back(string("1")); code_table[0].push_back(string("2"));
code_table[0].push_back(string("3"));


//以下从一字母的字串,逐级生成二字母,三字母......的字串
      for (i=0; i<DIGITS; i++)
      {
            append_c(code_table[i], code_table[i+1]);
            int check_n=(i/2)+1;
            for (int k=1; k<=check_n; ++k)    //k是检查的位数 1, 2...
                  v_str_check(code_table[i+1], code_table[i+1].size(), i+2, k);
      }  //这里是i+2,要小心

      int out_cnt=0;

      for (i=0; i<DIGITS; i++)
            for (j=0; j<code_table[i].size(); j++)
            {
                  cout<<setw(DIGITS+2)<<code_table[i][j];
                  out_cnt++;
                  if (!(out_cnt%5)) cout<<endl;
                  if (!(out_cnt%50)) system("pause");
                  }
      cout<<endl;
      system("pause");
      return 0;
      }

//---------------------------------------------------------------
int append_c(vector<string>&v1, vector<string>&v2)
{                                            //依据向量v1生成v2
      string str, str1;

      int v1size=v1.size(), v2size=0;
      for (int i=0; i<v1size; ++i)
      {
            str1=v1[i];
            for (int j=0; j<3; ++j)  
            {
                  str=str1;
                  str.push_back(j+'1');       //在末尾添加一个字母
                  v2.push_back(str);         //生成的字符串依次放入向量v2
                  v2size++;
            }
      }
       return v2size;
}
//---------------------------------------------------------------

//对给出的字符串进行unoverlap检查,就是对尾部的连续n位n位对比检查
//str长度不小于2n由函数外部保证
//返回true表示末尾两个n位相同
bool str_check(const char* str, int strlen, int n)
{
      int start1=strlen-2*n;
      int start2=start1+n;
      for (int i=start1; i<start2; i++)
            if (str[i]!=str[i+n]) return false;
      return true;
      }

void v_str_check(vector<string>&v, int size, int strlen, int n)
{
      for (vector<string>::iterator i=v.begin(); i<v.end(); ++i)
      {
            if (str_check((*i).c_str() , strlen, n))
                  {i=v.erase(i);i--; size--;} /////
            }
      }
//-----------------------------------------------------------------

测试通过了一些数据，大的数据就不知道了！
速度应该不会很好，用了回溯，大量的递归。

#include<iostream>
using namespace std;

#define MAX 1000       
#define N  30      

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 unoverlap(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;

}

int main(void)
{
    char *p=new char[MAX];
    
    unoverlap(N,p);

    for(int i=0;i<N;i++)
        cout<<p[i]<<" ";
    cout<<endl;
    return 0;
}

回溯法，每放一个数字判断是否会产生重复，按'1','2','3'的顺序放置，如果都不满足，则回退一个。
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 unoverlap(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 unoverlap(int n,char *p)
{
 char ch3[6][4]={{'1','2','3','\0'},{'1','3','2','\0'},{'3','1','2','\0'},{'3','2','1','\0'},{'2','3','1','\0'},'2','1','3','\0'}};
  char ch2[6][3]={{'1','2','\0'},{'1','3','\0'},{'2','3','\0'},{'2','1','\0'},{'3','2','\0'},{'3','1','\0'}};
  char ch1[4][2]={{'1','\0'},{'2','\0'},{'3','\0'}};
  int n1,n2,n3,pos3,count3,i,j;
  n3=n/3;             /*求得长度为3的子串个数*/
  n2=(n-3*n3)/2;   /*求长度为2的子串数*/
  n1=n-3*n3-2*n2;/*求长度为1的子串数*/
  count3=n3/6;
  i=count3;
  while(count3>0){
    for(i=0;i<6;i++)strcat(p,ch3[i]);/*循环将CH3中的字串接到P的后面*/
    count3--;}
   pos3=n3-6*i;
   for(i=0;i<pos3;i++)
      strcat(p,ch3[i]);
   for(i=0;ch2[i][0]==ch3[pos3-1][2];i++);
   strcat(p,ch2[i]);
   for(j=0;ch1[j][0]==ch2[i][1];j++);
   strcat(p,ch1[j]);
}

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 unoverlap(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);
}

/*
  Name: 
  Copyright: 
  Author: 
  Date: 18-05-07 21:28
  Description: 产生指定长度的无连续重复部分的字符串(所有元素都由'1','2','3'这三个字母构成)
输入: 指定的长度n
输出: 无
函数接口:
void unoverlap(int n, char *p)//p是已经分配好了的,不用担心溢出.
例如:
输入5
输出 p中的内容应为12312(或满足条件的其它串)
(不能输出12323,因为23和23是连在一起的并且相同)
当然只要输出一个满足条件字符串的就可以了。
*/

/*
算法思想： 构造一个指针数组lib，存储由'1','2','3'组合构成的所有子串（共6个），每个元素指向一个子串。
很明显满足条件的字符串是由lib中的子串组合而成。为避免出现连续重复部分，
这些子串的组合并不是任意的，每个子串后面只能接6个子串中的2个，比如lib[0]后只可以接lib[1]或lib[2]；而lib[1]后只可以接lib[0]或lib[4]。
构造一个二维数组a[][3]，其中a[][0]表示构成字符串p的子串在数组lib中的下标（即lib[a[i][0]]表示一个子串）；a[][1]和a[][2]表示可以接在子串lib[a[i][0]]后面的子串下标（有且仅有两个）。
先确定数组a的第一个元素值，之后可以从a[0][1]和a[0][2]随机选取一个值作为其后子串的下标，确定第2个元素。
依次确定数组a的所有元素----每加入一个元素要判断它是否与前面的子串连续重复，
判断的方法是取步长1-len/2（len表示数组a的当前长度）判断子串是否连续重复----最后把数组a对应的子串连接到字符串p中，并去掉多余的字符 。 
*/
#include <iostream>
using namespace std;

void unoverlap(int n, char *p);
void Create(int a[][3], int n, int k);
void Change(int a[][3], int n);
bool Cover(int a[][3], int n);
bool Compare(int a[][3], int n, int step);

int main()
{
    char a[6000] = {0};
    
    unoverlap(500, a);
    puts(a);
    
    getchar();
    return 0;
}

/*
函数功能：产生指定长度的无连续重复部分的字符串
输入变量：int n, 指定的字符串长度
          char *p， 存储最终结果的字符串
输出变量：char *p， 存储最终结果的字符串
返回值： 无 
*/
void unoverlap(int n, char *p)
{
    char *lib[6] = {"123", "132", "213", "231", "312", "321"};//存储由'1','2','3'构成的所有组合 
    const int MAX = n / 3 + 1;//数组a的长度，因为每个子串的长度为3，所以最多需要（n/3+1）个子串 
    int a[MAX][3];//存储子串信息的二维数组，具体含义参考算法思想 
    bool flag = false;//判断是否出现重复字符串，初始化为没有重复 
    int k;

    a[0][0] = 0;
    a[0][1] = 1;
    a[0][2] = 2;
    
    for (int i=1; i<MAX; )
    {
        if (flag)//若出现重复字符串，则需要修改数组a的栈顶元素
            Change(a, i);
        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;
            }
        }
    }

//    for (int i=0; i<MAX; ++i)
//        cout << lib[a[i][0]] << "  ";
//    cout<< endl;

    for (int i=0; i<MAX; ++i)//把数组a对应的子串连接到字符串p中 
        strcat(p, lib[a[i][0]]);
        
    p[n] = '\0';//去掉多余的字符 
}

/*
函数功能：根据当前数组的最后一个元素，产生一个新元素 
输入变量：int a[][3], 存储了子串信息的二维数组
          int n， 二维数组的长度 
          int k， 数组元素a[n-1][1]或a[n-1][2]中的一个，作为a[n][0]的值 
输出变量：int a[][3], 更新后的二维数组
返回值： 无 
*/
void Create(int a[][3], int n, int k)
{
    a[n][0] = k;
    
    switch (k)//根据k的值确定该子串后面可以接的子串，即a[n][1]或a[n][2]的值 
    {
        case 0 : a[n][1] = 1;
                 a[n][2] = 2;
                 break;
        case 1 : a[n][1] = 0;
                 a[n][2] = 4;
                 break;
        case 2 : a[n][1] = 0;
                 a[n][2] = 3;
                 break;
        case 3 : a[n][1] = 2;
                 a[n][2] = 5;
                 break;
        case 4 : a[n][1] = 5;
                 a[n][2] = 1;
                 break;
        case 5 : a[n][1] = 4;
                 a[n][2] = 3;
                 break;
    }
}

/*
函数功能：修改数组a的栈顶元素，改变a[n-1][0]的值，有且仅有两种选择 
输入变量：int a[][3], 存储了子串信息的二维数组
          int n， 二维数组的长度 
输出变量：int a[][3], 更新后的二维数组
返回值： 无 
*/
void Change(int a[][3], int n)
{
    if (a[n-1][0] == a[n-2][1])
        a[n-1][0] = a[n-2][2];
    else
        a[n-1][0] = a[n-2][1];
}

/*
函数功能：判断数组a是否出现连续重复元素，对应的可以知道字符串p是否出现连续重复部分 
输入变量：int a[][3], 存储了子串信息的二维数组
          int n， 二维数组的长度 
输出变量：无
返回值： 若出现连续重复元素，返回真，否则返回假 
*/
bool Cover(int a[][3], int n)
{
    for (int i=2; i<=n/2; ++i)//i表示被分析的子串的长度，大于1（因为连续的两个字符肯定不等），不超过n/2 
    {
        if (Compare(a, n, i))//判断长度为i的子串是否与其前面等长的子串相等，若相等则表示重复 
            return true;
    }
    return false;
}

/*
函数功能：判断数组a中长度为step的子序列（总是包含最后一个元素）是否与其前面等长的子序列相等，
输入变量：int a[][3], 存储了子串信息的二维数组
          int n， 二维数组的长度 
输出变量：无
返回值： 若子序列相等，返回真，否则返回假 
*/
bool Compare(int a[][3], int n, int step)
{
    for (int i=n-step; i<n; ++i)
    {
        if (a[i][0] != a[i-step][0])
            return false;
    }
    return true;
}

cc