字符串拆分

algorithm 阅读量

字符串拆分概论

某种字符串处理语言能够允许程序员将一个字符串拆分成为两段。由于此操作需要复制字符串，因此需要$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