Проверка на цикличность строки
Feb. 2nd, 2023 01:58 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoЯ тут решал какую-то задачу на литкоде, и одна из подзадач была:
Дано строка str1 и строка str2. Надо проверить, что строка str2 состоит из повторов строки str1. По решению большей задачи размер str2 гарантировано является кратным размеру str1, то есть нужно просто проверить, что str1 снова и снова повторяется в str2.
str1 и str2 - это [u8].
Два решения:
Похожий на сишный вариант с двойным циклом
Мой вариант:
В целом, дело не в экономии байт, а в логике: первое делает какую-то низкоуровневую циклическую арифметику с неиллюзорным шансом словить панику на out of bound access, а второе конструирует инвариант: мы сравниваем итераторы по str2 и по циклическому повторению str1 с размером, равным длине str2.
В целом, нам бы мог помочь Iterator.array_chunks, но он не стабильный пока что (то есть его ещё нет в стабильном rust'е).
Дано строка str1 и строка str2. Надо проверить, что строка str2 состоит из повторов строки str1. По решению большей задачи размер str2 гарантировано является кратным размеру str1, то есть нужно просто проверить, что str1 снова и снова повторяется в str2.
str1 и str2 - это [u8].
Два решения:
Похожий на сишный вариант с двойным циклом
str2.iter().enumerate().all(|(i, &b1)| b1 == str1[i % str2.len()]
Мой вариант:
str2.iter().eq(str1.iter().cycle().take(str2.len()))
В целом, дело не в экономии байт, а в логике: первое делает какую-то низкоуровневую циклическую арифметику с неиллюзорным шансом словить панику на out of bound access, а второе конструирует инвариант: мы сравниваем итераторы по str2 и по циклическому повторению str1 с размером, равным длине str2.
В целом, нам бы мог помочь Iterator.array_chunks, но он не стабильный пока что (то есть его ещё нет в стабильном rust'е).