a5_folding.cpp

该算法设计短小精悍

#include<stdio.h>
#include<string>
#include<iostream>
#include<vector>
using namespace std;
struct record{
	int num,value;
	string str;
};
struct record map[101][101];
int main() {
	string str,tmp_str,tmp_str2;
	char tmp[8];
	int i,j,k,l,value,min,o,p,x,y;
	int list[101][101],len[101]={0};
	for (i=2;i<=100;i++) 
		for (j=1;j<i;j++)
			if (i%j==0)
				list[i][len[i]++]=j;
	while(cin>>str) {
		l=str.length();
		for (i=0;i<l;i++) {
			if (i==0){
				for (j=0;j<l;j++) {
					map[j][i].num=map[j][i].value=1;
					map[j][i].str=str[j];
				}
			}else {
				for (j=0;j<l-i;j++) {
					min=1000;
					for (k=0;k<i;k++) {
						if (map[j][k].num==1) tmp_str=map[j][k].str;
						else {
							sprintf(tmp,"%d",map[j][k].num);
							tmp_str2=tmp;
							tmp_str=tmp_str2+"("+map[j][k].str+")";
						}
						if (map[j+k+1][i-k-1].num==1) tmp_str=tmp_str+map[j+k+1][i-k-1].str;
						else {
							sprintf(tmp,"%d",map[j+k+1][i-k-1].num);
							tmp_str2=tmp;
							tmp_str=tmp_str+tmp_str2+"("+map[j+k+1][i-k-1].str+")";
						}
						value=tmp_str.length();
						if (value<min) {
							min=value;
							map[j][i].num=1;
							map[j][i].str=tmp_str;
							map[j][i].value=value;
						}
					}
					for (k=0;k<len[i+1];k++) {
						x=list[i+1][k];
						y=(i+1)/x;
						for (p=0;p<x;p++)
							for (o=1;o<y;o++) 	 
								if (str[j+p]!=str[j+o*x+p]) goto next;
						sprintf(tmp,"%d",y);
						tmp_str2=tmp;
						value=map[j][x-1].value+tmp_str2.length()+2;
						if (value<min) {
							min=value;
							map[j][i].num=y;
							map[j][i].str=map[j][x-1].str;
							map[j][i].value=value;
						}
next:;
					}
				}
			}
		}
		if (map[0][l-1].num==1) cout<<map[0][l-1].str<<endl;
		else cout<<map[0][l-1].num<<"("<<map[0][l-1].str<<")"<<endl;
	}
	return 0;
}