字符串拆分

字符串拆分概论

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

主要的拆分方式如下；

自底向上非递归求解

算法分析：

break_string2.h

#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

#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);
}

算法实现结果

自顶向下递归算法

记得带备忘机制

break_string.h

//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

#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)$

算法实现结果