#/*program string ABC */#include <iostream>#include <string>#include <conio.h>#include <cstdio>#include <iomanip>using namespace std;const int maxx = 100;int N, MinC;char X[maxx], Best[maxx];int T[maxx]; /*T[i] cho biet so kí tu "C" trong doan tù X[1] -> X[i]*//*Hàm Same (i, L ) cho biet xau gòm 1 kí tu ket thuc tai X[i] có trùng vói xau1 kí tu lien truoc nó hay ko*/bool Same ( int i, int L ){ int j = i - L; /*j là vi trí cuoi doan lien truoc doan dó*/ for ( int k = 0; k < L; k++ ) { if ( X[i-k] != X[j-k] ) { return false; } } return true;}/*Hàm Check cho biet X[i] có làm hong tính lap cua dãy X[1..i] hay không*/bool Check ( int i ){ for ( int L = 1; L <= i/2; L++ ) /*Thu các do dài L*/ { if ( Same (i,L)== true ) /*Néu có xau do dài L ket thúc boi X[i] bi trùng vói xâu lièn truóc*/ { return false; } } return true;}/*Giu lai két qua tìm dc vào BestConfig ( MinC và mãng Best )*/void KeepResult(){ MinC = T[N]; for ( int i = 0; i <= N; i++ ) { Best[i] = X[i]; }}/*Thuat toán quay lùi nhánh can*/void Branch_Bound ( int i ){ char j; for ( j = 'A'; j <= 'C'; j++ ) { X[i] = j; if ( Check(i) == true ) /*Néu them giá tri vào dó ko làm hong tính lap*/ { if ( (T[i] + (N-i)/4 ) < MinC ) /*Dánh giá*/ { if ( j == 'C' ) { T[i] = T[i-1] + 1; /*Tính T[i] qua T[i-1]*/ } else { T[i] = T[i-1]; } if ( i == N ) KeepResult(); else Branch_Bound(i + 1); } } }}void PrintResult(){ for ( int i = 1; i <= N; i++ ) { cout << Best[i]; } cout << endl; cout << " Minimum letter C : " << MinC << endl;} int main(){ cout << "Enter the length of string "; cin >> N; T[0] = 0; MinC = N; Branch_Bound(1); PrintResult(); system("pause"); return 0;}