字符串拆分

字符串拆分概论

某种字符串处理语言能够允许程序员将一个字符串拆分成为两段。由于此操作需要复制字符串,因此需要$n$个时间单位来将一个$n$个字符串拆分为两段。假定一个程序员希望将一个20个字符的字符串在第2个,第8个,以及第10个字符串进行从左到右拆分。

主要的拆分方式如下;

01

02

03

自底向上非递归求解

算法分析:

04

break_string2.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;

#define n 7 //为L[]的数组元素的个数

int break_string_array(int L[],int cut[][n+1])
{
int cost[n+1][n+1]={0};

for(int len=2;len<=n;len++)
{
for(int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
if(j-i>1)
cost[i][j]=0x7fffffff;
for(int part=i+1;part<j;part++)
{
int value=cost[i][part]+cost[part][j]+(L[j-1]-L[i-1]);
//注意,这里cost[start][part]+cost[part+1][end]会发生错误
if(value<cost[i][j])
{
cost[i][j]=value;
cut[i][j]=part;
}
}
}
}
return cost[1][n];
}

void print_breaks(int L[],int cut[][n+1],int i,int j)
{
if(j-i>=2)
{
int k=cut[i][j];
cout<<L[k-1]<<" ";
print_breaks(L,cut,i,k);
print_breaks(L,cut,k,j);
}
}

break_string2.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "break_string2.h"

int main()
{
//int L[n]={0,2,8,10,20};
int L[n]={0,11,14,17,20,25,30};
int cut[n+1][n+1]={0};

int result=break_string_array(L,cut);
cout<<"result is : "<<endl;
cout<<result<<endl;

print_breaks(L,cut,1,n);
}

算法实现结果

05

自顶向下递归算法

记得带备忘机制

break_string.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//L[]表示拆分点数组
//cost[][]表示花费

#include <iostream>
#define INFINITY 0x7fffffff
using namespace std;

#define m 5
#define n 30
using namespace std;

//int position[n+1][n+1]={0};

int cost[n+1][n+1]={0};
int exist[n+1][n+1]={0};

int total_cost=INFINITY;
int part=0;
int cut_point=0;

void INITIATE(int cost[][n+1])
{
for(int i=0;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
cost[i][j]=INFINITY;
}
}

//break_point中,start,end分别表示下标起始坐标,尾坐标
int break_point(int L[],int cost[][n+1],int start,int end,int cut[][n+1]) //start end表示第几个数,而不是数组下标
{
//使用递归判断的时候要先看看在start和end之间是否存在这样的值
if(end-start<2)
{
cost[start][end]=0;
return cost[start][end];
}
if(cost[start][end]!=INFINITY)
return cost[start][end];

for(int i=0;i<m;i++)
{
if(L[i]>start && L[i]<end)
{
exist[start][end]=1;
break;
}
}

if(exist[start][end]==0)
{
cost[start][end]=0;
return cost[start][end];
}
else
{
int total_cost=INFINITY;
for(int i=0;i<m;i++)
{
if(L[i]>start && L[i]<end)
{
part=L[i];
if(break_point(L,cost,start,part,cut)+break_point(L,cost,part+1,end,cut)+(end-start+1)<=total_cost)
{
total_cost=break_point(L,cost,start,part,cut)+break_point(L,cost,part+1,end,cut)+(end-start+1);
cut_point=i;
}
}
}
if(total_cost<=cost[start][end])
{
cost[start][end]=total_cost;
cut[start][end]=cut_point;
}
}
return cost[start][end];
}

void print_breaks(int L[],int cut[][n+1],int start,int end)
{
if(exist[start][end]==1)
{
cout<<L[cut[start][end]]<<" ";

print_breaks(L,cut,start,L[cut[start][end]]);
print_breaks(L,cut,L[cut[start][end]]+1,end);
}
}

break_string.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "break_string.h"


int main()
{
//int L[m]={2,8,10};
int L[m]={11,14,17,20,25};
int cost[n+1][n+1];
int cut[n+1][n+1]={0};

INITIATE(cost);
//初始化完毕

int result=break_point(L,cost,1,n,cut);
print_breaks(L,cut,1,n);

cout<<endl;
cout<<"The result is :";
cout<<result<<endl;
return 0;

}

这里注意的是递归式和自底向上方法不一样

$ if(breakpoint(L,cost,start,part,cut)+breakpoint(L,cost,part+1,end,cut)+(end-start+1)<=totalcost)$

算法实现结果

06