PHP中的平衡自动换行（最小的不整洁度）

PHP中的平衡自动换行（最小的不整洁度）

用C ++快速又脏

#include <sstream>#include <iostream>#include <vector>#include <cstdlib>#include <memory.h>using namespace std;int cac[1000][1000];string res[1000][1000];vector<string> words;int M;int go(int a, int b){    if(cac[a][b]>= 0) return cac[a][b];    if(a == b) return 0;    int csum = -1;    for(int i=a; i<b; ++i){    csum += words[i].size() + 1;    }    if(csum <= M || a == b-1){    string sep = "";        for(int i=a; i<b; ++i){ res[a][b].append(sep); res[a][b].append(words[i]); sep = " ";    }    return cac[a][b] = (M-csum)*(M-csum);    }    int ret = 1000000000;    int best_sp = -1;    for(int sp=a+1; sp<b; ++sp){    int cur = go(a, sp) + go(sp,b);    if(cur <= ret){        ret = cur;        best_sp = sp;    }    }    res[a][b] = res[a][best_sp] + "n" + res[best_sp][b];    return cac[a][b] = ret;}int main(int argc, char ** argv){    memset(cac, -1, sizeof(cac));    M = atoi(argv[1]);    string word;    while(cin >> word) words.push_back(word);    go(0, words.size());    cout << res[0][words.size()] << endl;}

测试：

$ echo "The quick brown fox jumps over a lazy dog" |./a.out 10The quickbrown foxjumps overa lazy dog

编辑：只是在Wikipedia页面上查看了最低程度的衣衫wrap的自动换行。将算法更改为给定算法（惩罚为平方）