Необходимо выводить только подстроки, повторяющиеся дважды подряд

@qwertyo1 · Регистрация: 21.02.2017

Author24 — интернет-сервис помощи студентам

Уже довольно много времени провел в попытках реализовать данный алгоритм, пока что безуспешно. Либо не работает, либо работает не так как нужно.
Цель: выводить только подстроки, повторяющиеся дважды подряд.
Примеры:
5643564312564 -> 56435643
фыывугуга -> ыыугуг
12344321 -> 44
22222222 -> 22222222
Спасибо заранее за подсказки.

@TopLayer · 21.02.2017, 04:44

Сформулируйте более точно, а то возникают неоднозначности:
bbb -> ? bb, bbb
ababbab -> ? (ab)(ab), (bab)(bab)
aabaabbaab -> ? (aab)(aab)(a)(a), (a)(a)(a)(a)(b)(b)(a)(a), (a)(a)(baab)(baab)

@qwertyo1 · 21.02.2017, 07:25 **[ТС]**

bbb -> bb
ababbab -> (bab)(bab)
aabaabbaab -> (a)(a)(baab)(baab)
Приоритет у более длинных цепочек. Спасибо.

@qwertyo1 · 24.02.2017, 17:04 **[ТС]**

TopLayer, не уверен, увидели ли вы мое сообщение. Недавно на форуме, прошу прощения.

@TopLayer · 24.02.2017, 18:40

qwertyo1, я видел ваше сообщение, но решать эту задачу мне было лень. Расскажу-ка я вам лучше алгоритм решения, а вы уж сами закодируйте. Итак, алгоритм:
1) Найти все двойные подстроки, сформировав список таких объектов:

C#

class DoubledStringInfo
{
    public int StartIndex;
    public int Length;
};

В решении этого пункта может помочь одна из перегрузок метода string.CompareOrdinal

2) Создать массив, содержащий лучшее решение для каждого префикса строки, индекс - длина префикса

C#

1 2	var bestSolutions = new string[input.Length + 1]; bestSolutions[0] = "";

3) Заполнить предыдущий массив. bestSolutions[i] = лучшее из:
а) bestSolutions[i-1]
б) для каждой двойной строки, заканчивающейся на индексе i (doubledString.StartIndex + doubledString.Length - 1 == i),
выбрать bestSolutions[doubledString.StartIndex] + input.Substring(doubledString.StartIndex, doubledString.Length)
4) Ответом на задачу будет bestSolutions[input.Length]

@qwertyo1 0 / 0 / 0 Регистрация: 21.02.2017 Сообщений: 9
		1
	Необходимо выводить только подстроки, повторяющиеся дважды подряд 21.02.2017, 01:43. Показов 1552. Ответов 4 Метки нет (Все метки) Уже довольно много времени провел в попытках реализовать данный алгоритм, пока что безуспешно. Либо не работает, либо работает не так как нужно. Цель: выводить только подстроки, повторяющиеся дважды подряд. Примеры: 5643564312564 -> 56435643 фыывугуга -> ыыугуг 12344321 -> 44 22222222 -> 22222222 Спасибо заранее за подсказки. 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	21.02.2017, 04:44	2
	Сформулируйте более точно, а то возникают неоднозначности: bbb -> ? bb, bbb ababbab -> ? (ab)(ab), (bab)(bab) aabaabbaab -> ? (aab)(aab)(a)(a), (a)(a)(a)(a)(b)(b)(a)(a), (a)(a)(baab)(baab) 0

@qwertyo1 0 / 0 / 0 Регистрация: 21.02.2017 Сообщений: 9
	21.02.2017, 07:25 [ТС]	3
	bbb -> bb ababbab -> (bab)(bab) aabaabbaab -> (a)(a)(baab)(baab) Приоритет у более длинных цепочек. Спасибо. 0

@qwertyo1 0 / 0 / 0 Регистрация: 21.02.2017 Сообщений: 9
	24.02.2017, 17:04 [ТС]	4
	TopLayer, не уверен, увидели ли вы мое сообщение. Недавно на форуме, прошу прощения. 0

	24.02.2017, 18:40

Необходимо выводить только подстроки, повторяющиеся дважды подряд

Решение