/** * Given a string, write a program to find out the longest substring. * Make sure the same letter should be next to each other. * Print the length of the logest substring. * Maybe you ought to print the substring with the smallest dictionary order. */ #include <cstdio> #include <cstring> #include <algorithm> #ifndef ONLINE_JUDGE #define FILEIO #endif // ONLINE_JUDGE #ifdef FILEIO FILE *infile=fopen("seq.in","r"), *outfile=fopen("seq.out","w"); #define scanf(x...) fscanf(infile,x) #define printf(x...) fprintf(outfile,x) #endif // FILEIO int n,k,tpe,dp[1<<13][14],bt[1<<13][14]; /// dp(i)[j][k] means with the i-th letter of the string chosen and ending with letter k, the length of the longest subsequence under j, which is the set containing letters chosen. /// bt[j][k] is the position(i) where dp(i)[j][k] get its value. char str[3101]; inline int change(char t) { return 1<<(t-'a'); } struct Node { Node* nxt; char chr; Node() { nxt=0x0; } }*rt[1<<12][13],*p; /// rt is the back string. inline Node* add(int i,int j,char chr) { if(rt[i][j]==NULL) { rt[i][j]=new Node; rt[i][j]->chr='\0'; } p=new Node; p->chr=chr; p->nxt=rt[i][j]->nxt; return rt[i][j]->nxt=p; } inline Node* add(int i,int j,int x,int y) { if(rt[i][j]==NULL) { rt[i][j]=new Node; rt[i][j]->chr='\0'; } if(rt[x][y]) rt[i][j]->nxt=rt[x][y]->nxt; p=new Node; p->chr=j-1+'a'; p->nxt=rt[i][j]->nxt; return rt[i][j]->nxt=p; } inline void print(int,int); int main() { scanf("%d%d%d",&n,&k,&tpe); scanf("%s",str); std::reverse(str,str+n); memset(dp,0x80,sizeof(dp)); dp[0][0]=0; rt[0][0]=new Node; rt[0][0]->chr='\0'; const int mxn=1<<k; for(int i=0;i<n;++i) { const int tmp=change(str[i]),tmp2=str[i]-'a'+1; for(int j=0;j<mxn;++j) if(j&tmp and dp[j][tmp2]>0) { dp[j][tmp2]+=1; add(j,tmp2,str[bt[j][tmp2]]); bt[j][tmp2]=i; } for(int j=0;j<mxn;++j) { if(j&tmp) continue; else { int mx=0; for(int p=1;p<=k;++p) { if(str[i]-'a'+1==p) continue; // dp[j|tmp][tmp2]=std::max(dp[j|tmp][tmp2],dp[j][p]+1); if(dp[j][p]>dp[j][mx]) mx=p; } if(dp[j|tmp][tmp2]<=dp[j][mx]) { dp[j|tmp][tmp2]=dp[j][mx]+1; add(j|tmp,tmp2,j,mx); bt[j|tmp][tmp2]=i; } else if(dp[j|tmp][tmp2]==dp[j][mx]+1 and mx<tmp2) { add(j|tmp,tmp2,j,mx); bt[j|tmp][tmp2]=i; } } } } int ans1,ans2; ans1=ans2=0; for(int i=0;i<mxn;++i) for(int j=1;j<=k;++j) if(dp[i][j]>dp[ans1][ans2] or (dp[i][j]==dp[ans1][ans2] and j<ans2)) ans1=i,ans2=j; printf("%d\n",dp[ans1][ans2]); if(tpe) print(ans1,ans2); #ifdef FILEIO fclose(infile); fclose(outfile); #endif // FILEIO return 0; } inline void print(int i,int j) { if(!rt[i][j]) return; p=rt[i][j]->nxt; while(p) { printf("%c",p->chr); p=p->nxt; } printf("\n"); } #ifdef FILEIO #undef scanf #undef printf #endif // FILEIO