Другие языки программирования и технологии

Помогите пожалуйста написать программу в с++

доброго вечера, может кто помочь написать программу ? ломаю голову уже не первый день, и даже зная что нужно делать все равно не получается это запрограммировать, если не сложно помогите пожалуйста
Задан массив символов A[n]. Найти самую длинную повторяющуюся последовательность символов и переписать ее в отдельный массив
Просто найти длиннейшую последовательность - это я могу, но вот повторяющуюся минимум 2 раза - с этим у меня проблемы . .
Вариант решения у меня есть, но все равно не получается, вот вариант :
Ищем первую последовательность. Проходим массив до конца, в поиске точно такой же последовательности (во внутреннем цикле). Если найдена, сохраняем ее в переменную максимальной последовательности, создаем переменную хранящую ее размер. Дальше во внешнем цикле ищем следующую последовательность символов. И снова во внутреннем ищем, повторяется она или нет. Если повторяется, то сравниваем ее размер, с размером максимальной сохраненной в переменную. Если она длиннее, то заменяем массив с максимальной последовательностью на новую, если нет - оставляем без изменений. Таким образом, дойдя во внешнем цикле до конца, мы получим в нашем массиве самую длинную последовательность.
То есть в примере введенного массива a b c K L M N k q w K L M N, здесь последовательность будет к л м н, для проверки я использовал массив на 26 элементов в котором был английский алфавит, потом проверял значение введенного символа на его порядковый номер в алфавите, и записывал. Далее вводилось 2 значение, и так же находился его порядковый номер, и если этот порядковый номер при проверке на -1 был равен предыдущему символу- значит символ идет последовательно, и делал так до конца пока проверка на последовательность не становилась неверной, указав координаты начала последовательности и конца - которые при 2 совпадающем символе я начал считать, записывал эту последовательность в массив, и записывал ее размер вида конец минус начало в отдельную переменную получая количество символов в массиве, потом находя след. последовательность проделывал то же самое, сравнивал размер с тем что записан в максимальную, и если больше то заменял. А вот при минимум 2 повторах я бессилен . .надеюсь на вашу помощь, заранее спасибо
И если возможно - используйте не сильно профессиональные варианты написания отдельных строк в программе, т.к с многими из них я еще не сталкивался, и очень проблематично разбираться что они значат.
АБ
Алексей Бондарович
88
Не знаю, правильно ли понял задачу?
Пусть имеется последовательность: "0123491239", видно что в ней ровно два повторяющихся участка, это последовательности символов "123", т. о. задача и состоит в их нахождении.
Если это так, то довольно легко такую задачу решить, используя шаблонные алгоритмы:

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
cout << "n? ";
int n;
cin >> n;

cout << "seq? ";
char *a = new char[n];
for (int i = 0; i < n; ++i) cin >> a[ i];

char *m = new char[n / 2];

int mn = 0;
for (int cn = 1; cn <= n / 2; ++cn) {
for (char *pc = a; pc < a + n - cn - cn; ++pc) {
if (search(pc + cn, a + n, pc, pc + cn) != a + n) {
copy(pc, pc + cn, m);
mn = cn;
break;
}
}
}
if (mn) {
cout << "seq: ";
for (int i = 0; i < mn; ++i) cout << m[ i];
}
delete [] a;
delete [] m;
return 0;
}
Ильнар Идиатуллин
Ильнар Идиатуллин
96 810
Лучший ответ
это похоже на одну из задач поиска синхроимпульса
можно это сделать разными способами, но проще для данного варианта использовать разностный метод при смещении копии последовательности, относительно несмещённой. Наибольшее количество нулей в результирующей разности будет признаком где искать и какой период повторения у повторяющейся последовательности
ВМ
Владимир Мусалимов
76 473
> Задан массив символов A[n]. Найти самую длинную повторяющуюся последовательность символов и переписать ее в отдельный массив

Дальше многа букаф, не асилил
Мой вариант на C++:

#include <iostream>
#include <iterator>
#include <locale>

#include <algorithm>
#include <functional>

template <typename>
void find_longest(I begin, I end, U u)
{
typedef typename std::iterator_traits::difference_type difference_type;

I next, first = begin, found = end;
difference_type max_seq = 0;

for ( ; (next = std::adjacent_find(begin, end, u)) != end; begin = ++next)
{
const difference_type curr_length = std::distance(begin, next) + 1;
if (curr_length > max_seq)
{ max_seq = curr_length; found = begin; }
}

const difference_type last_length = std::distance(begin, next);
if (last_length > max_seq)
{ max_seq = last_length; found = begin; }

typedef typename std::iterator_traits::value_type T;
typedef std::ostream_iterator<t> O;

std::cout << "Исходная последовательность: " << std::endl;
std::copy(first, end, O(std::cout, " "));
std::cout << std::endl;

std::cout << "Самая длинная последовательность: " << std::endl;
std::copy(found, found + max_seq, O(std::cout, " "));
std::cout << std::endl;
}

struct R
{
int operator()() const
{
return rand() % 21 - 10;
}
};

int main()
{
setlocale(LC_ALL, "");
srand((unsigned) time(NULL));

int arr[20];
std::generate_n(arr, sizeof(arr) / sizeof(arr[0]), R());

find_longest(arr, arr + sizeof(arr) / sizeof(arr[0]), std::not2(std::equal_to<int>()));

return 0;
}

Демонстрация: hxxp://codepad. org/rhgt3DPV
Виктор Грамматиков
Виктор Грамматиков
1 769

Похожие вопросы