Как определить, является ли строка слишком длинной в O (1) времени сложности?

Question

Я пытаюсь увидеть, превышает ли строка 10000 символов. если это так, он должен вывести too long. Я знаю, что могу сделать это с strlen, но тогда временная сложность составляет O(n), что не так уж и плохо, но мне все равно приходится каждый раз перебирать 10000 символов, если кто-то вводит 10000 символов, но если кто-то мой вводит 1 миллион символов, что плохо n. Поэтому я решил проверить, установлен ли 10,001-й символ. Если он установлен, то он явно слишком длинный. Будет ли это работать? Или это иногда сработает (и зависит от того, как была выделена память).

Answer 1

Я знаю, что могу сделать это с помощью strlen, но тогда временная сложность O (n)

Я не знаю, кто вам это говорит, strlen просто возвращает свойство len.

Определение strlen , используется макрос ZSTR_LEN для получения длины строки

ZEND_FUNCTION(strlen)
{
    zend_string *s;

    ZEND_PARSE_PARAMETERS_START(1, 1)
        Z_PARAM_STR(s)
    ZEND_PARSE_PARAMETERS_END();

    RETVAL_LONG(ZSTR_LEN(s));
}

И определение ZSTR_LEN

#define ZSTR_LEN(zstr) (zstr)->len

Answer 2

<?php 
if (isset($str[100001])) { 
     ... do my stuff ... 
} ?> 

Функция isset выполняется на $ str [10001], который является только одним адресом в массиве, следовательно, o [1].Кроме того, при обращении к ключу из индекса в php, он не выдает ошибку и не вызывает утечку памяти.Он генерирует исключение OutOfBoundsException, которое может быть перехвачено блоком try catch.

Answer 3

strlen уже имеет временную сложность O (1), поскольку длина просто сохраняется как атрибут.

http://php.net/manual/en/function.strlen.php

Answer 4

Использование substr

substr(yourString, lengthConstraint, 1);