Алгоритм: Разделите строку на части N с помощью пробелов, таким образом, все части имеют почти ту же длину
Я ищу алгоритм, который берет строку и разделяет ее на определенное число частей. Эти части должны содержать полные слова (таким образом, пробелы будут использоваться для разделения строки), и части должны иметь почти ту же длину или содержать самые длинные части.
Я знаю не то, чтобы трудно кодировать функцию, которая может сделать то, что я хочу, но интересно, существует ли доказанный и алгоритм FAST с этой целью?
править: Для разъяснения моего вопроса, я опишу Вас проблема, которую я пытаюсь решить.
Я генерирую изображения с фиксированной шириной. В эти изображения я пишу использованию имен пользователей GD и Freetype в PHP. Так как у меня есть фиксированная ширина, я хочу разделить имена на 2 или 3 строки, если они не вписываются в тот.
Для заполнения как можно большего количества пространства, я хочу разделить имена способом, что каждая строка содержит как можно больше слова. С этим я подразумеваю, что в одной строке должны быть так же слова как необходимый для хранения длины каждой строки близко к средней длине строки целого текстового блока. Таким образом, если существует одно длинное слово и два коротких слова, эти два коротких слова должны стоять на одной строке, если это делает все строки о равном долго.
(Затем я вычисляю ширину текстового блока с помощью 1, 2 или 3 строки и если она вписывается в мое изображение, я представляю ее. Просто, если существует 3 строки, и это не будет соответствовать, я уменьшаю размер шрифта, пока все не прекрасно.)
Пример: This is a long text должен быть дисплей что-то как этот:
This is a
long text
или:
This is
a long
text
но нет:
This
is a long
text
и также нет:
This is a long
text
Надежда я мог объяснить более ясный, что я ищу.
5 ответов
Если вы говорите о переносе строк, взгляните на Dynamic Line Breaking , который дает решение динамического программирования для разделения слов на строки.
Рабочие коды Python
- Wrap.py - Разбивать абзацы на строки, пытаясь избежать коротких строк.
- SMAWK.py - То же самое в
O (n)
кодах Дэвида Эпштейна .
Способ переноса слов обычно заключается в размещении как можно большего количества слов в одной строке и переходе к следующей, когда места больше нет. Это, конечно, предполагает, что вы имеете в виду максимальную ширину.
Независимо от того, какой алгоритм вы используете, имейте в виду, что если вы не работаете со шрифтом фиксированной ширины, вам нужно работать с физической шириной слова, а не с количеством букв.
Не знаю, как насчет проверенных, но кажется, что самым простым и эффективным решением будет разделить длину строки на N, затем найти ближайшее белое пространство к местам разделения (поиск нужно вести как вперед, так и назад).
Приведенный ниже код, кажется, работает, хотя есть много условий ошибки, которые он не обрабатывает. Кажется, что он будет выполняться за O(n), где n - количество нужных строк.
class Program
{
static void Main(string[] args)
{
var s = "This is a string for testing purposes. It will be split into 3 parts";
var p = s.Length / 3;
var w1 = 0;
var w2 = FindClosestWordIndex(s, p);
var w3 = FindClosestWordIndex(s, p * 2);
Console.WriteLine(string.Format("1: {0}", s.Substring(w1, w2 - w1).Trim()));
Console.WriteLine(string.Format("2: {0}", s.Substring(w2, w3 - w2).Trim()));
Console.WriteLine(string.Format("3: {0}", s.Substring(w3).Trim()));
Console.ReadKey();
}
public static int FindClosestWordIndex(string s, int startIndex)
{
int wordAfterIndex = -1;
int wordBeforeIndex = -1;
for (int i = startIndex; i < s.Length; i++)
{
if (s[i] == ' ')
{
wordAfterIndex = i;
break;
}
}
for (int i = startIndex; i >= 0; i--)
{
if (s[i] == ' ')
{
wordBeforeIndex = i;
break;
}
}
if (wordAfterIndex - startIndex <= startIndex - wordBeforeIndex)
return wordAfterIndex;
else
return wordBeforeIndex;
}
}
Вывод для этого:
1: This is a string for
2: testing purposes. It will
3: be split into 3 parts