Вот некоторые мысли, которые, несмотря на все мои старания, не обернутся в поклон. Тем не менее, они могут быть полезной отправной точкой для чьего-либо анализа.
Рассмотрим предложенное решение следующим образом. Это тот подход, который предложили несколько человек, включая меня в предыдущей версии этого ответа. :)
- Обрезать начальные и конечные нули.
- Сканирование строки в поисках 1.
- Когда 1 найден:
- Предположим, что это середина 1 решения.
- Для каждого предыдущего 1 используйте сохраненную позицию, чтобы вычислить ожидаемую позицию финала 1.
- Если вычисленная позиция находится после конца строки, она не может быть частью решения, поэтому исключите эту позицию из списка кандидатов.
- Проверьте решение.
- Если решение не найдено, добавьте текущий 1 в список кандидатов.
- Повторяйте, пока не будет найдено больше 1.
Теперь рассмотрим строки входных строк, подобные приведенным ниже, которые не будут иметь решения:
101
101001
1010010001
101001000100001
101001000100001000001
В общем, это конкатенация k строк в форме j 0, за которыми следует 1 для j от нуля до k-1.
k=2 101
k=3 101001
k=4 1010010001
k=5 101001000100001
k=6 101001000100001000001
Обратите внимание, что длины подстрок равны 1, 2, 3 и т. Д. Итак, размер задачи n имеет подстроки длиной от 1 до k, такие что n = k (k + 1) /2.
k=2 n= 3 101
k=3 n= 6 101001
k=4 n=10 1010010001
k=5 n=15 101001000100001
k=6 n=21 101001000100001000001
Обратите внимание, что k также отслеживает количество единиц, которые мы должны рассмотреть. Помните, что каждый раз, когда мы видим 1, нам нужно учитывать все 1, увиденные до сих пор. Поэтому, когда мы видим вторую 1, мы рассматриваем только первую, когда мы видим третью 1, мы пересматриваем первые две, когда мы видим четвертую 1, нам нужно пересматривать первые три, и так далее. К концу алгоритма мы рассмотрели k (k-1) / 2 пары единиц. Назовите это p.
k=2 n= 3 p= 1 101
k=3 n= 6 p= 3 101001
k=4 n=10 p= 6 1010010001
k=5 n=15 p=10 101001000100001
k=6 n=21 p=15 101001000100001000001
Соотношение между n и p таково, что n = p + k.
Процесс прохождения строки занимает O (n) времени. Каждый раз, когда встречается 1, выполняется максимум (k-1) сравнений. Поскольку n = k (k + 1) / 2, n> k ** 2, то sqrt (n)> k. Это дает нам O (n sqrt (n)) или O (n ** 3/2). Тем не менее, обратите внимание, что это не может быть очень жесткой границей, потому что количество сравнений идет от 1 до максимум k, это не k за все время. Но я не уверен, как объяснить это в математике.
Это все еще не O (n log (n)). Кроме того, я не могу доказать, что эти данные являются худшими, хотя я подозреваю, что это так. Я думаю, что более плотная упаковка 1 в передней части приводит к еще более редкой упаковке в конце.
Так как кто-то может все еще найти это полезным, вот мой код для этого решения на Perl:
#!/usr/bin/perl
# read input as first argument
my $s = $ARGV[0];
# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";
# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;
# prime the position list with the first '1' at position 0
my @p = (0);
# start at position 1, which is the second character
my $i = 1;
print "the string is $s\n\n";
while ($i < length($s)) {
if (substr($s, $i, 1) eq '1') {
print "found '1' at position $i\n";
my @t = ();
# assuming this is the middle '1', go through the positions
# of all the prior '1's and check whether there's another '1'
# in the correct position after this '1' to make a solution
while (scalar @p) {
# $p is the position of the prior '1'
my $p = shift @p;
# $j is the corresponding position for the following '1'
my $j = 2 * $i - $p;
# if $j is off the end of the string then we don't need to
# check $p anymore
next if ($j >= length($s));
print "checking positions $p, $i, $j\n";
if (substr($s, $j, 1) eq '1') {
print "\nsolution found at positions $p, $i, $j\n";
exit 0;
}
# if $j isn't off the end of the string, keep $p for next time
push @t, $p;
}
@p = @t;
# add this '1' to the list of '1' positions
push @p, $i;
}
$i++;
}
print "\nno solution found\n";