Всем доброго времени. Есть следующее задание: назовем строку палиндромом, если она одинаково читается слева направо и справа налево. Примеры палиндромов: «abcba», «55», «q», «xyzzyx». Требуется для введенной строки найти максимальную по длине ее подстроку, являющуюся палиндромом.
Есть код:
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include "stdafx.h"
#include <iostream>
#include <string>
#include <clocale>
using namespace std;
int main()
{
setlocale(LC_ALL, "rus");
cout << "Введите строку-палиндром для вывода её максимальной подстроки: ";
string str;
getline (cin, str);
int size = str.length();
int max = 1;
int i = 1; //середина палиндрома;
int count = 1;
int j = 1; //первый знак палиндрома (при несимметричном палиндроме);
int k = 0; //первый знак палиндрома (при симметричном палиндроме);
int start;
while ((i - j) >= 0 && (i + j) < size) { //чтобы не выйти за пределы массива;
if (str[i - j] == str[i + j]) { //сравниваем символы, стоящие справа и слева от i-того;
count+=2; //длина палиндрома увеличивается на 2 символа;
j++;
if (count > max){
max = count;
}
else { //если палиндром кончился, то передвигаем его середину на следующий элемент;
j = 1;
count = 1;
i++;
}
}
i = 0;
count = 0;
while ((i - k) >= 0 && (i + j) < size) { //чтобы не выйти за пределы массива;
if (str[i - k] == str[i + j]) { //сравниваем i-тый и соседний справа от i-того символ;
count += 2; //если символы одинаковые, то прибавить 2 к длине палиндрома;
j++;
k++;
if (count > max)
max = count;
}
else { //если палиндром кончился, то передвигаем его середину на следующий элемент;
k = 0;
j = 1;
count = 0;
i++;
}
}
if (k>j) //если k больше, то палиндром симметричен и должен начинаться с k;
start = k;
else //если j больше, то палиндром несимметричен и должен начинаться с j;
start = j;
cout << str.substr(start, max) << endl; //вывести подстроку, начинающуюся с найденного начала строки start и с найденной длинной max
system("pause");
return 0;
}
} |
|
Количество символов max находит нормально, а с параметром start я совладать не могу. Подскажите, как нормализовать это? Программа вместо палиндрома выводит что-то очень нелицеприятное в виде совсем не тех кусков строки. Заранее спасибо!
(
