Rust-строковое

[amarao]

А вот строки в Rust'е неожиданно сложны. Например, такая простая вещь, как strstr() (поиск начала подстроки в строке) с каждой итераций раздумий всё сложнее и сложнее. Особенно, если делать эффективно.

Во-первых, мы не можем иметь индекс в строку, потому что размер символа в строке плавает. Во-вторых любые байтовые операции не применимы для вычисления индекса, потому что байты в индекс превращаются нетривиальным образом.

Итератор chars не очень хороший, потому что он из любого символа (даже 1-байтового) делает 4 байта. Это значит, что для поиска подстроки в гигабайтной строке нам нужно будет перемолотить 4 ГБ в режиме записи (вероятнее всего, в регистр, но всё равно...)

Т.е. первая задача, которая у нас будет, это реализация считающего Window поверх String/str без копирования. Внутри это указатель на первый символ и байтовая длина (при том, что количество символов в window фиксировано, байтовый размер будет прыгать очень неровно).

Основываться она должна на str-итераторе по символам. Такой итератор получает &str, после чего начинает возвращать &str в один символ (in-place, без копирования!). Т.е. ещё уровнем ниже, это fat pointer на байты строки, который указывает на начало символа и содержит в себе его длину, кроме того, он содержит в себе (для удобства, видимо), адрес начала строки, и её оригинальный размер.

Перед тем, как изобретать всё своё с нуля, надо ещё раз перечитать что String и str умеют из коробки (игнорируя существование find и matches, разумеется).

Чем глубже я в это погружаюсь, тем тоньшее все нюансы становятся. Я чувствую, что пока что я сделаю очень грубо, с использованием Vec.

.. Сделал. Получил заслуженные 40мс (нижние 27% всех решений). Нырять в устройства fat pointers я пока не готов.

pub fn str_str(haystack: String, needle: String) -> i32 {
    if needle.len() == 0 {return 0};
    let haystack_vec: Vec<char> = haystack.chars().collect();
    let needle_vec: Vec<char> = needle.chars().collect();
    let mut pos = 0;
    for candidate in haystack_vec.windows(needle_vec.len()){
        if candidate == needle_vec.as_slice(){
            return pos as i32;
        }
        pos += 1;
    }
    -1
}