Найти кратчайший префикс в строке в C

Question

Я новичок в C и буду благодарен за вашу помощь в коде. Мне нужно выделить динамически массив и проверить, какой префикс в строке является самым коротким, что это конкатенация, строит строку и печатает ее и ее длину.

Вот несколько примеров выходов:

1. для «ABABAB», вывод должен быть: «AB» длина 2
2. для «АААА», вывод должен быть: «а "длина 1
3. для "abcaabca", вывод должен быть: "ABCA" длина 4
4. для "ABCDEFG", вывод должен быть: "ABCDEFG" длина 7
5. для "acacaac" выход должен быть «acacaac» длиной 7

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

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

Благодаря

Answer 1

Я не буду писать эффективный код, но сама идея.

Во-первых, этот «префикс» вашего имеет длину, которая является делителем большой длины. Поэтому, если длина i префикса не делит длину n строки, она должна быть пропущена.

Чтобы проверить правильность длины i, вам необходимо сравнить символы из позиций j и j + i для всех возможных значений j.

Answer 2

Это может быть довольно просто, две вложенные петли, внешняя - для, от 1 до длины/2 и внутренней a while, с использованием указателя, увеличенного на каждом шаге на значение переменной итерации внешний контур. Внутри цикла вы можете использовать strncmp() для сравнения правильной подстроки и разбить цикл, если сравнение не выполняется. Если все сравнения в порядке, вы нашли «самый короткий префикс», чтобы вы могли разбить цикл (for). Цикл for также может быть оптимизирован путем пропускания длин, которые не являются делителями длины входной строки.

Для этого не требуется копирование или копирование.

И да, я оставлю вас на самом деле написать код.

Answer 3

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

1- Найти количество различных символов в строке, используя массив логических. Пусть это число равно x.

2- проверить, являются ли первые символы x префиксами. (проверьте положение каждой позиции p на p + x, p + 2x и т. д.). Если неудачный, самый короткий префикс - целая строка.

В промежутке вы можете сделать это быстрее, быстро проверив, если x делит на длину строки ..