Есть задача с палиндромами, но нужно исправить использование стандартного словаря на написанный
#include <iostream>
#include <string>
#include <map>
int palindrome_substr( std::string str )
{
std::map<std::string, int> hash_table;
int n = str.size();
// Вспомогательный массив для хранения радиусов найденных палиндромов, одна строка для палиндромов чётной длины, другая для нечётной
int T[2][n + 1];
// Расширим исходную строку для предотвращения выхода за её пределы в процессе поиска
str = "@" + str + "#";
for ( int j = 0; j <= 1; j++ )
{
int rp = 0; // радиус палиндрома
T[j][0] = 0;
int i = 1;
while ( i <= n )
{
// Пытаемся расширить палиндром из позиции i как центра
while ( str[i - rp - 1] == str[i + j + rp] )
rp++;
T[j][i] = rp;
int k = 1;
while ( (T[j][i - k] != rp - k) && (k < rp) )
{
T[j][i + k] = std::min( T[j][i - k], rp - k );
k++;
}
rp = std::max( rp - k, 0 );
i += k;
}
}
str = str.substr( 1, n );
// Вставка всех найденных палиндромов и одобуквенных строк в хэш-таблицу:
hash_table[ std::string( 1, str[0] ) ] = 1;
for (int i = 1; i <= n; i++ )
{
for ( int j = 0; j <= 1; j++ )
for (int rp = T[j][i]; rp > 0; rp-- )
hash_table[ str.substr(i - rp - 1, 2 * rp + j) ] = 1;
hash_table[ std::string(1, str[i]) ] = 1;
}
// Вывод самих палиндромов
std::map<std::string, int>::iterator iter;
for ( iter = hash_table.begin(); iter != hash_table.end(); ++iter )
std::cout << (*iter).first << std::endl;
return hash_table.size() - 1;
}
int main()
{
std::string str = "aba gfd hyf gfdfg";
std::cout << "Строка: '" << str << "' \n";
int number = palindrome_substr( str );
std::cout << "\nКоличество палиндромов в строке: "
<< number << std::endl;
return 0;
}
Есть задача с палиндромами, но нужно исправить использование стандартного словаря на написанный