a5.cpp

第二届全国高校 BBS 程序开发大赛算法组

#include <iostream>
#include <string>
using namespace std;
#include <stdlib.h>
#include <memory.h>

string GetShortestStr(string strin);

void main()
{
	string str;
	cin>>str;
	cout<<GetShortestStr(str);
}

/***************************************************************************************
                          　函数名称：GetShortestStr
							函数作用：返回最短折叠序列
							输入：源字符串　　
							输出：最短折叠序列

		                             [算法简介]
		 　 a)对于长为n的源字符串strin,依次将最左端开始的1,2,...n/2个字符构成的字串
		 作为当前子串进行处理。
		 　 b)处理时首先计算当前子串自源字串自最左端开始的连续重复次数num，若整个源字
		 串均为本子串的连续重复，则对本子串简单处理后直接返回。否则，当前子串对应了
		 源字串的两种分段方式：
		 　　1.当前子串自最左端开始的所有连续重复+源字串的剩余部分，例：
		 　　　　当前子串为abc时,abcabcabcjoiyouo分段为(abcabcabc + joiyouo)
		     2.当前子串自最左端开始的部分连续重复+源字串的剩余部分，这种分段方式要满足
		 以下条件：子串在源子串剩余部分左端开始的连续重复加上其后某一段长度大于0的字串后，
		 所得到的新字串能马上找到连续的重复，例：
		       当前子串为ab时,ababababcdabcd可分段为(ababab +abcdabcd)，而不可分段为
		　(abab + ababcdabcd)因为abcd在源字串剩余部分的最左端是有连续重复的，而ababcd没有
		　　　对于所有对应sign数组项等于false的分段方式，实施分段操作
            c)用sign数组纪录某分段处理的必要性，避免重复处理,当当前节点处理完毕后,将sign
		 数组中序号小于(num*2*本子串长度)的项置为true
		                           
****************************************************************************************/

string GetShortestStr(string strin)
{
	int length = strin.length();
	if (length<5)
		return strin;
	
	char numrestore[4] = {0,0,0,0};               //用于存储数字到字符串的转换结果
	bool *sign = new bool[length];                //标志当前分段是否需要处理，false表示需要
	memset((void*)sign,0,length*sizeof(bool));

	string strout = strin;	                      //纪录当前找寻的最短折叠序列
	int minlength = length;                       //记录当前最短长度
	
	string curstr,tempstr;                        //记录当前处理字串以及临时字串存储
	int calnum,*cal = new int[length];            //纪录当前子串对应分段数目以及各分段的分割点
	
    for (int i = 0; i<length/2; ++i)
	{
		curstr = GetShortestStr(strin.substr(0,i+1));
		
		//得到当前子串自源字串最左端开始的连续重复次数
		int num = 1;
		while (strin.substr(0,i+1)==strin.substr(num*(i+1),i+1)){
			if ((++num)==length/(i+1))
				break;
		}		

		//子串处理部分
		if (num*(i+1)==length)    
		{
			if ((num-1)*(i+1)>3)
			{
				itoa(num,numrestore,10);
			    tempstr = numrestore;
				tempstr += '('+curstr+')';
				return tempstr;
			}
			else 
				return strin;
		}
		else 
		{
			cal[0] = num; calnum = 0;
			string reststr = strin.substr(num*(i+1),length-num*(i+1));
			int restnum = 0,pos;
			tempstr = strin.substr((num-1)*(i+1),i+2);
            while ((pos = reststr.find(tempstr))!=-1 && restnum<num){
				tempstr = strin.substr(0,i+1)+tempstr;
				++restnum;
				if ((strin.substr((num-restnum)*(i+1),pos+restnum*(i+1))==
					strin.substr(pos+num*(i+1),pos+restnum*(i+1))) && restnum<num){					
                     cal[++calnum] = num-restnum; 
				}				
            }
			for (int j = 0; j<=calnum; ++j)
			{
				if (!sign[cal[j]*(i+1)-1])
				{
	    			if (cal[j]*(i+1)>3+i+1)
					{
	  		        	itoa(cal[j],numrestore,10);
			            tempstr = numrestore;
			         	tempstr += '('+curstr+')';
					}
		        	else
					{
			        	tempstr = curstr;
		             	for (int k = 1; k<cal[j]; ++k)
		  
							tempstr += curstr;
					}
			     	tempstr += GetShortestStr(strin.substr(cal[j]*(i+1),length-cal[j]*(i+1)));
			     	if (tempstr.length() < minlength){
		         		minlength = tempstr.length();
		        		strout = tempstr;
					}
				}
			}			

			//对sign数组进行处理
			for (j = 0; j<num*2*(i+1) && j<length; ++j)
				sign[j]=true;
		}
	}
	
	//内存回收
	delete cal;
	delete sign;
	
	return strout;	
}