Если она выглядит, как показано - что мешает пробежать от начала до первой заглавной буквы?

А вдруг попадётся камень и ключ будет с двумя заглавными?

Вначале кандидат в первом случае «C», следующий отрезок длины(«С») не совпадает с «C», увеличиваем кандидата до тех пор, пока он не совпадёт.

Тогда можно посмотреть в сторону суфиксных деревьев

Неправильный алгоритм.

AaAaBbAaAaBb

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

QString section(...) или wxStringTokenizer

Надо жадно значит идти, до тех пор, пока длина кандидата не станет не меньше половины.

Предлагаю такой алгоритм:

Начинаешь брать с конца последовательности по одному символу и сравнивать полученную последовательность с началом исходной.

ТабуретТабуретТабуретТабуретТабу -> р
ТабуретТабуретТабуретТабуретТаб  -> ур
ТабуретТабуретТабуретТабуретТа   -> бур
ТабуретТабуретТабуретТабуретТ    -> абур
ТабуретТабуретТабуретТабурет     -> Табур

Так ты найдешь наибольшую повторяющуюся последовательность (строка слева). Затем применяешь к ней этот же алгоритм рекурсивно пока не сможешь выделить никакую последовательность. Оставшаяся строка будет наименьшей повторяющейся последовательностью.

Как-то так.

пока длина кандидата не станет не меньше половины

AbAbAbAbAbAbAbAbAbAbAbAbCdAbAb

Не прокатит

И вот эта C разве находится в строке?

AbAbAbAbAbAbAbAbAbAbAbAbCdAbA -> b
AbAbAbAbAbAbAbAbAbAbAbAbCdAb -> Ab // совпадение, начинаем сначала

AbAbAbAbAbAbAbAbAbAbAbAbCdA -> b
AbAbAbAbAbAbAbAbAbAbAbAbCd -> Ab // совпадение, начинаем сначала

AbAbAbAbAbAbAbAbAbAbAbAbC -> d
AbAbAbAbAbAbAbAbAbAbAbAb -> Cd
AbAbAbAbAbAbAbAbAbAbAbA -> bCd
AbAbAbAbAbAbAbAbAbAbAb -> AbCd
...
A -> bAbAbAbAbAbAbAbAbAbAbAbCd
ничего -> AbAbAbAbAbAbAbAbAbAbAbAbCd // больше ничего - это последовательность

Итого, последовательность : AbAbAbAbAbAbAbAbAbAbAbAbCd

Лови
// gcc main.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char str[]=«BlaBlyaBlaBlyaBlaBlyaBlaBlyaBla»;
char key[128];

int n=1;

GetKey()
{
char * pos=strstr(&str[n],key);
if(pos>0)
{
if(strlen(key)==(pos-str))
{
printf(«Find period %d, key %s\n»,strlen(key),key);
} else
{
strncpy(key,str,pos-str);
GetKey();
}

} else

printf(«ERROR NOT FIND %s\n»,key);
}

void main(void)
{
key[n-1]=str[n-1];
key[n]=0;
GetKey();
}

Regexp backreference?

char str[]=«BlaBlyaBlaBlyaBlaBlyaBlaBlyaBla»;

работает, но

char str[]=«BlaBlyaBlaBlyaBlaBlyaChortBlaBlyaBla»;

не работает - Find period 7, key BlaBlya

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

Отныне это тред-детектор первокурсников.

ЗЫ: печатает 14, что неверно даже для заданного примера.

А какой ответ здесь должет быть ? Если честно не очень-то врубился в условия задачи.

Нифика, это тред-детектор систематизаторов тредов

Все верно. Печатается количество байт в ключе. Ограничений на набор символов не вижу. Возможно в качестве ключа используются японские иероглифы.

Мне интересно, что предложат, не хочу свой велосипед городить с нуля.

Да что тут придумывать? Есть алгоритм быстрого поиска подстроки в строке, на его основе _очень_ быстро получается решение вашей задачи. Что тут еще думать?

Так ведь должно быть 7, а не 14

Ну раз Вам это ясно и понятно, предлагаю Вам удалиться из моего треда подальше и наблюдать из своей берлоги. Премного благодарен, спасибо за помощь.

Точно, как говаривают программеры на дельфях пойду искать компонент рисующий тигрёнка.

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

Пользуясь тегом Qt предлагаю вам такое:

#include <QCoreApplication>
#include <iostream>

const QString orig="AbcAbcCdeAbcAbcCdeFghAbcAbcCdeAbcAbcCdeFghAbcAbcC";

bool notCycle(const QList<QChar> &arg1, const QList<QChar> &arg2) {
    bool cycle=false;
    for(int i=0; i!=arg1.size() && i!=arg2.size(); ++i)
        if (arg1.at(i)!=arg2.at(i)) cycle=true;
    return cycle;
}

QList<QChar> mostLongCycle(QList<QChar> &arg) {
    QList<QChar> back;
    QList<QChar> orig=arg;

    do {
        if (arg.size()>0) back.push_front(arg.takeLast());
        else return back;
    } while (notCycle(orig, back));

    return back;
}


QList<QChar> fillList(const QString& str) {
    QList<QChar> res;
    for(int i=0; i!=str.size(); ++i)
        res.push_back(str.at(i));
    return res;
}

int main(int argc, char *argv[])
{
    QList<QChar> key;
    QList<QChar> prev;
    QList<QChar> str=fillList(orig);
    if (argc>1) str=fillList(QString(argv[1]));

    do {
        prev=key;
        key=mostLongCycle(str);
    } while (str.size()>0);

    // Против циклических ключей
    if (!notCycle(key, prev) && key.size()!=prev.size()) key+=prev;

    for(int i=0; i!=key.size(); ++i) std::cout << key.at(i).toAscii();
    std::cout << std::endl;
}

В строке «Табурет» при использовании кодировки utf-8 14 байт, но 7 символов.

Ну дак, взаимно же.

Автокорреляционную функцию посчитай

От оно че... Тем не менее, у вас ключ должен быть не меньше половины строки. А если ключ длиннее? AbcAbcCdeAbcAbcCdeFghAbcAbcCde и ключ не найден.

Чуток исправил

int main(int argc, char *argv[])
{
    QList<QChar> key;
    QList<QChar> prev;
    QList<QChar> str=fillList(orig);
    if (argc>1) str=fillList(QString(argv[1]));

    int round=0;
    do {
        prev=key;
        key=mostLongCycle(str);
        ++round;
    } while (str.size()>0);

    // Против циклических и вида 'ротор'
    if ( round>2 && !notCycle(key, prev) && key.size()!=prev.size())  key+=prev;

    for(int i=0; i!=key.size(); ++i) std::cout << key.at(i).toAscii();
    std::cout << std::endl;
}

BlaBlyaBlaBlyaBlaBlyaChort

А почему тогда ключиком не считать «BlaBlyaBlaBlyaBlaBlyaChortBlaBlyaBla» целиком ? Остальное не убралось. Откуда такая уверенность что именно «BlaBlyaBlaBlyaBlaBlyaChort» ?

зы. Это шифрование Цезарь использовал вообще с одной буквой, потом монахи. Были любители среди них себя поистязать, но не до такой же степени. И ключ они запиской открытым текстом передавали или устно. С трудом представляю как можно ключ «дятелдятелдят» сообщить клиенту. Выбраковывать надо такие ключи при вводе как ошибочные и не париться.

А почему тогда ключиком не считать «BlaBlyaBlaBlyaBlaBlyaChortBlaBlyaBla» целиком ?

Потому, что ТС хочет получить самый короткий вариант ключа, что вполне логично, т.к. зашифрованный текст может быть очень длинным, а ключ коротким. Зачем же брать ключ длинной равный тексту, если можно взять только наименьшую повторяющуюся часть?

С трудом представляю как можно ключ «дятелдятелдят» сообщить клиенту. Выбраковывать надо такие ключи при вводе как ошибочные и не париться.

У ТС обратная задача, он имея открытый и закрытый текст находит текст с циклически повторяющимся ключём. Нужно выделить из текста наименьшую циклическую часть (т.е. ключь как он был задан при зашифровке).

Для определения ключа он должен полностью повторятся как минимум два раза. Т.е. в последовательности «12312» ключом может быть как «123» так и «12312», зависит от последующих символов.

У меня стоит условие как минимум два повторения + хотя бы один символ. Возможно достаточно проверять только 2 повторения, т.е. «for(int i = 1; i <= len/2; i++)» в main. Зависит от задачи.

Для определения ключа он должен полностью повторятся как минимум два раза

Кто сказал? Ключ может вообще не повторяться.

После небольших раздумий ко мне пришёл в голову подобный алгоритм: http://rghost.ru/42914369

bool Subkey::checkKey(int keyStart) const {
    QString key1 = key.left(keyStart);
    QString key2 = key.right(key.length() - keyStart);
    bool result = false;

    if (key2.startsWith(key1) || key1.startsWith(key2)) {
        // try to tile keystring with found key1
        QString keySnapshot;
        while (keySnapshot.length() < key.length()) {
            keySnapshot += key1;
        }
        result = keySnapshot.startsWith(key);
    }

    return result;
}


void Subkey::output() {
    int keyEnd = -1;

    for (int i = 1; i < key.length(); i++) {
        if (key[0] == key[i] && checkKey(i)) {
            keyEnd = i;
            break;
        }
    }

    if (keyEnd != -1) {
        QString keyword = key.left(keyEnd);
        std::cout << "Key is: " << keyword.toStdString() << std::endl;
    } else {
        std::cout << "Key was not found in: " << key.toStdString() << std::endl;
    }
}

Неисповедимы пути ТСа, ориентируюсь на это
http://school-555.narod.ru/kript/5.htm там речь про слова.
Само слово при известном полностью ключе представляет собой чисто игровой интерес, расшифровать и показать.

зы. Вот в ключе олололололололо ,кстати, какое ключевое слово ?

Хотел поизобретать велосипедов, но понял, что, в общем, буду заниматься тем же, что и no-such-file

Что мешает тупо в лоб решить задачу?

#!/usr/bin/python3

def check_tiling(tile, s):
	repetitions = len(s) // len(tile)
	appendix_len = len(s) % len(tile)
	return s == tile * repetitions + tile[:appendix_len]

def get_min_tile(s):
	for i in range(1, len(s)):
		tile = s[:i]
		if check_tiling(tile, s):
			return tile
	return s

print(get_min_tile('СтулСтулСтулСтулСтулСтулСт'))

Вот в ключе олололололололо ,кстати, какое ключевое слово ?

Если я правильно понял ТСа, то «ол»... Логично же выбрать наименьший ключ...

Ага, именно такой. В общем задача решена, алгоритм на моём наборе данных работает, а на остальных вообще пофигу.

pls see gasfild string for more

у тя задача факторизации строки с возможным остатком(префиксом ключа)

лобовое решение квадратично(линейное удлинение пробы начиная с 1 символа и вплоть до всей строки*проверка )

решение используещее суффиксное дерово - nlogn?

если учесть что ключ есть всегда ....

Это я к тому, что в общем случае понять какой период на таких данных нельзя, от «oл» до «олололололололо» . Идея то сначала была здравая, писать с большой буквы начало ключевого слова и первый исходник из 5 строк эту задачу решал. Можно конечно еще 5 дописать и будет работать и с повторяющимися подстроками внутри ключа. Но конечно классы,шаблоны, qt и проч. на такую задачку это пять, это впечатляет. Зря ржут на дельфистами-видузятниками, когда они чтобы линию нарисовать гуглят компонент «рисовальщик линий», ой зря.

Посчитай префикс-функцию для строки (та, что в алгоритме Кнута-Морриса-Пратта юзается). Её значение на последнем символе будет меньше длины строки как раз на длину повторяющейся последовательности.

Работает за O(длина строки).

да забей ты на этого trex6 - судя по его комментам, это вообще тролль какой-то.

Но конечно классы,шаблоны, qt и проч. на такую задачку это пять, это впечатляет. Зря ржут на дельфистами-видузятниками, когда они чтобы линию нарисовать гуглят компонент «рисовальщик линий», ой зря.

Конечно зря. А вот за ваше char key[128] я бы сразу расстреливал.