Если бы я занялся этим, я сделал бы это следующим образом.
Я думаю, что все это связано с подсчетом чередующихся серий «1» и «0», обработкой серии «1» с последующим прогон '0' как пары, затем разбив список этих пар.
Давайте начнем со сканирования до первого «1» и установки начальной позиции s . Затем подсчитайте каждый прогон '1's c1 и следующий прогон' 0's c0 , создавая пары (c1, c0) .
. сканирование затем продолжается вперед до конца, оборачивая при необходимости. Если мы представляем серии из 1 или более '1' и '0' как однозначные числа, а '|' как начало и конец строки, то у нас есть следующие случаи:
|10101010|
^ initial start position s -- the string ends neatly with a run of '0's
|1010101|
^ new start position s -- the string starts and ends in a '1', so the first
run of '1's and run of '0's are rotated (left),
to be appended to the last run of '1's
Note that this changes our start position.
|01010101|
^ initial start position s -- the first run of '0's is rotated (left),
to follow the last run of '1's.
|010101010|
^ initial start position s -- the first run of '0's is rotated (left),
to be appended to the last run of '0's.
Примечание: если строка начинается и заканчивается на '1', изначально есть n серии «0» и « n + 1 * 1021» серии «1», но при вращении это число уменьшается до «1022 * n » «1». И аналогично, но наоборот, если строка начинается и заканчивается на «0».
Давайте используем A в качестве сокращения для пары (a1, a0) . Предположим, у нас есть другая пара, X - (x1, x0) - затем можно сравнить две пары, таким образом:
- , если a1> x1 или ( a1 = x1 и ( a0 ) => A> X - A - это лучше начать
- , если a1 = x1 и a0 = x0 => A = X
- , если a1 или ( a1 = x1 и ( a0> x0 ) => A - X лучше начало
Уловка, вероятно, состоит в том, чтобы упаковать каждую пару в целое число - скажем, (x1 * N) - x0 , где N - по крайней мере максимально допустимая длина строки - для удобства сравнения.
Во время сканирования строки (описанного выше) построим вектор пар. Во время этого процесса соберем наибольшее значение пары A и список позиций с каждого появления A . Каждый с в списке является потенциальной наилучшей стартовой позицией. ( записанный s должен быть индексом вектора пар и смещением в исходной строке.)
[Если входная строка действительно обширна, тогда строится полный вектор всех пар будет есть память. В этом случае вектор должен быть обработан как «виртуальный» вектор, а когда требуется элемент в этом векторе, он должен быть создан путем чтения соответствующей части фактической строки.]
Теперь:
Упростим группы из двух или более смежных A . Ясно, что второй и последующие A в такой группе не могут быть лучшим началом, так как есть более лучший сразу слева. Таким образом, при сканировании нам нужно записать только s для первых A таких групп.
, если строка начинается с единицы или более A и заканчивается одним или несколькими A , необходимо «повернуть», чтобы собрать их в одну группу, и записать s только для самых левых A в этой группе (обычным способом).
Если в списке только один s , наш работа сделана. Если строка является сквозной A , она будет здесь указана.
В противном случае нам необходимо рассмотреть пары, следующие за каждой из s для наши (начальные) A - где, когда мы говорим «следовать», мы включаем переход от конца к началу строки (и, что эквивалентно, список пар).
NB: на данный момент мы знаем, что за всеми (начальными) A в нашем списке следуют ноль или более A , а затем по крайней мере один х , где х <А </em>.
Итак, установите i = 1 и рассмотрите все пары в s + i для нашего списка s . Оставьте только s для экземпляров самой большой найденной пары. Таким образом, для i = 1 в этом примере мы рассматриваем пары x, y и z :
- . ..Ax .... Az ... Az..Ax ... Ay ...
И если x является наибольшим, этот проход сбрасывает Ay и оба Az . Если останется только один s - в примере, y - самый большой - наша работа завершена. В противном случае повторите для i = i + 1 .
Есть одна последняя (я думаю) морщина. Предположим, что после нахождения z наибольшей из ih пар мы имеем:
где два прогона === совпадают друг с другом. По тому же логу c, который велел нам игнорировать второй и последующие A в тех же сериалах, теперь мы можем отказаться от второго A === z . Действительно, мы можем отказаться от третьего, четвертого и т. Д. c. смежных A === z . К счастью, это касается крайнего случая (скажем):
где Строка - это последовательность A === z !
Я не знаю, что все кажется сложнее, чем я ожидал, когда изложил карандашом и бумагой: - (
Я предполагаю, что кто-то намного умнее, чем я, может свести это к некоторой стандартной величайшей проблеме со строкой префикса.
Мне было скучно сегодня, поэтому я выбил некоторый код (и пересмотрел его 10 -Apr-2020).
typedef unsigned int uint ; // assume that's uint32_t or similar
enum { max_string_len = 5 * 100000 } ; // 5 * 10^5
typedef uint64_t pair_t ;
static uint
one_zero(const char* str, uint N)
{
enum { debug = false } ;
void* mem ;
size_t nmx ;
uint s1, s0 ; // initial run of '1'/'0's to be rotated
uint s ;
pair_t* pv ; // pair vector
uint* psi ; // pair string index
uint* spv ; // starts vector -- pair indexes
uint pn ; // count of pairs
uint sn ; // count of starts
pair_t bp ; // current best start pair value
uint bpi ; // current best start pair index
uint bsc ; // count of further best starts
char ch ;
if (N > max_string_len)
{
printf("*** N = %u > max_string_len (%u)\n", N, max_string_len) ;
return UINT_MAX ;
} ;
if (N < 1)
{
printf("*** N = 0 !!\n") ;
return UINT_MAX ;
} ;
// Decide on initial start position.
s = s1 = s0 = 0 ;
if (str[0] == '0')
{
// Start at first '1' after initial run of '0's
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '0's !!
}
while (str[s] == '0') ;
s0 = s ; // rotate initial run of '0's
}
else
{
// First digit is '1', but if last digit is also '1', need to rotate.
if (str[N-1] == '1')
{
// Step past the leading run of '1's and set length s1.
// This run will be appended to the last run of '1's in the string
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '1's !!
}
while (str[s] == '1') ;
s1 = s ; // rotate initial run of '1's
// Step past the (now) leading run of '0's and set length s0.
// This run will be appended to the last run of '1's in the string
//
// NB: we know there is at least one '0' and at least one '1' before
// the end of the string
do { s += 1 ; } while (str[s] == '0') ;
s0 = s - s1 ;
} ;
} ;
// Scan the string to construct the vector of pairs and the list of potential
// starts.
nmx = (((N / 2) + 64) / 64) * 64 ;
mem = malloc(nmx * (sizeof(pair_t) + sizeof(uint) + sizeof(uint))) ;
pv = (pair_t*)mem ;
spv = (uint*)(pv + nmx) ;
psi = (uint*)(spv + nmx) ;
pn = 0 ;
bp = 0 ; // no pair is 0 !
bpi = 0 ;
bsc = 0 ; // no best yet
do
{
uint x1, x0 ;
pair_t xp ;
psi[pn] = s ;
x1 = x0 = 0 ;
do
{
x1 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : '\0' ;
}
while (ch == '1') ;
if (ch == '\0')
{
x1 += s1 ;
x0 = s0 ;
}
else
{
do
{
x0 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : '\0' ;
}
while (str[s] == '0') ;
if (ch == '\0')
x0 += s0 ;
} ;
// Register pair (x1,x0)
reg:
pv[pn] = xp = ((uint64_t)x1 << 32) - x0 ;
if (debug && (N == 264))
printf("si=%u, sn=%u, pn=%u, xp=%lx bp=%lx\n", psi[sn], sn, pn, xp, bp) ;
if (xp > bp)
{
// New best start.
bpi = pn ;
bsc = 0 ;
bp = xp ;
}
else
bsc += (xp == bp) ;
pn += 1 ;
}
while (ch != '\0') ;
// If there are 2 or more best starts, need to find them all, but discard
// second and subsequent contiguous ones.
spv[0] = bpi ;
sn = 1 ;
if (bsc != 0)
{
uint pi ;
bool rp ;
pi = bpi ;
rp = true ;
do
{
pi += 1 ;
if (pv[pi] != bp)
rp = false ;
else
{
bsc -= 1 ;
if (!rp)
{
spv[sn++] = pi ;
rp = true ;
} ;
} ;
}
while (bsc != 0) ;
} ;
// We have: pn pairs in pv[]
// sn start positions in sv[]
for (uint i = 1 ; sn > 1 ; ++i)
{
uint sc ;
uint pi ;
pair_t bp ;
if (debug && (N == 264))
{
printf("i=%u, sn=%u, pv:", i, sn) ;
for (uint s = 0 ; s < sn ; ++s)
printf(" %u", psi[spv[s]]) ;
printf("\n") ;
} ;
pi = spv[0] + i ; // index of first s+i pair
if (pi >= pn) { pi -= pn ; } ;
bp = pv[pi] ; // best value, so far.
sc = 1 ; // new count of best starts
for (uint sj = 1 ; sj < sn ; ++sj)
{
// Consider the ith pair ahead of sj -- compare with best so far.
uint pb, pj ;
pair_t xp ;
pb = spv[sj] ;
pj = pb + i ; // index of next s+i pair
if (pj >= pn) { pj -= pn ; } ;
xp = pv[pj] ;
if (xp == bp)
{
// sj is equal to the best so far
//
// So we keep both, unless we have the 'A==zA==z' case,
// where 'z == xp == sp', the current 'ith' position.
uint pa ;
pa = pi + 1 ;
if (pa == pn) { pa = 0 ; } ; // position after first 'z'
// If this is not an A==zA==z case, keep sj
// Otherwise, drop sj (by not putting it back into the list),
// but update pi so can spot A==zA==zA===z etc. cases.
if (pa != pb)
spv[sc++] = spv[sj] ; // keep sj
else
pi = pj ; // for further repeats
}
else if (xp < bp)
{
// sj is less than best -- do not put it back into the list
}
else
{
// sj is better than best -- discard everything so far, and
// set new best.
sc = 1 ; // back to one start
spv[0] = spv[sj] ; // new best
pi = pj ; // new index of ith pair
bp = xp ; // new best pair
} ;
} ;
sn = sc ;
} ;
s = psi[spv[0]] ;
free(mem) ;
return s ;
}
Я проверил это по методу грубой силы, приведенному в другом месте, и, насколько я вижу, это (сейчас, 10 апреля-2020) рабочий код.
Когда я рассчитал это на своей машине, для 100 000 случайных строк из 400 000..500 000 символов (случайным образом) я получил:
Brute Force: 281.8 secs CPU
My method: 130.3 secs CPU
, и это исключает 8,3 секунды для построения случайной строки и запустить пустой тест. (Это может звучать много, но для 100 000 строк по 450 000 символов, в среднем, это прикосновение менее 1 CP U цикл на символ.)
Так что для случайных строк мой сложный метод чуть более чем в два раза быстрее, чем грубая сила. Но он использует ~ N * 16 байтов памяти, где метод грубой силы использует N * 2 байта. Учитывая приложенные усилия, результат не очень радует.
Однако я также попробовал два патологических случая: (1) повторное «10» и (2) повторное «10100010» и только для 1000 (не 100000) строки из 400 000 ... 500 000 символов (в случайном порядке), которые я получил:
Brute Force: (1) 1730.9 (2) 319.0 secs CPU
My method: 0.7 0.7 secs CPU
Это O (n ^ 2) будет убивать вас каждый раз!