字符串拆分概论
某种字符串处理语言能够允许程序员将一个字符串拆分成为两段。由于此操作需要复制字符串,因此需要$n$个时间单位来将一个$n$个字符串拆分为两段。假定一个程序员希望将一个20个字符的字符串在第2个,第8个,以及第10个字符串进行从左到右拆分。
主要的拆分方式如下;
自底向上非递归求解
算法分析:
break_string2.h
|
|
break_string2.cpp
|
|
算法实现结果
自顶向下递归算法
记得带备忘机制
break_string.h
|
|
break_string.cpp
|
|
这里注意的是递归式和自底向上方法不一样
$ if(breakpoint(L,cost,start,part,cut)+breakpoint(L,cost,part+1,end,cut)+(end-start+1)<=totalcost)$