Строка из одинаковых подстрок

11 Август 2019 - Время чтения: 11 минуты

Условие задачи: Дана строка символов. Определить, состоит ли она из одинаковых подстрок. Например, строка "abcabc" состоит из двух подстрок abc. В качестве результата вывести длину подстроки. Если строку возможно разбить несколькими способами, вывести максимальную длину. Например, "abababab" считается состоящей из двух "abab", а не четырёх "ab". Если строку невозможно разбить таким образом, вывести ноль.

Примеры работы:
abaaba → 3
ababab → 2
aaaaaa → 3
aaaaa → 1
aaaab → 0

Решение: Будем проверять каждую возможную подстроку, начиная с наибольшей. Для этого нужно выяснить, на какие числа (включая 1) делится длина строки. Сначала попытаемся разделить строку пополам, т.е. проверим, делится ли её длина L на L / 2. Потом будем уменьшать делитель до единицы. Точнее, потенциальный делитель, потому что надо ещё проверить делимость. Каждый раз будем сравнивать первую часть строки со всеми остальными частями.


Программа на языке C99
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(void)
{
    size_t len = 0;
    char *str = calloc(1, sizeof(char));
    for (int ch; (ch = getchar()) != EOF && ch != '\n';) {
        str[len] = (char)ch;
        str = realloc(str, ++len + 1);
        str[len] = '\0';
    }
    size_t i;
    for (i = len / 2; i != 0; --i) {
        if (len % i != 0) continue;
        size_t j;
        for (j = i; j < len; j += i) {
            if (memcmp(str, str + j, i) != 0) break;
        }
        if (j == len) break;
    }
    printf("%u\n", (unsigned)i);
    return 0;
}

Программа на языке Python
s = input()
i = len(s) // 2
while i != 0:
    if len(s) % i == 0 and all(s[:i] == s[j:j+i] for j in range(i, len(s), i)):
        break
    i -= 1
print(i)

Решение получилось очень простое, но меня не покидает ощущение, что оно неоптимальное. Сложность алгоритма получается квадратичная. Если у Вас есть идеи, как сделать лучше - пишите в комментариях! Будем думать вместе.

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории