Сколько палиндромов можно образовать путем выбора символов из строки?

Во-первых, решение вашего друга, похоже, содержит ошибку, поскольку strchr может выполнять поиск за пределами max. Даже если вы исправите это, решение будет экспоненциальным во времени.

Для более быстрого решения вы можете использовать динамическое программирование, чтобы решить эту проблему за время O (n ^ 3). . Для этого потребуется O (n ^ 2) дополнительной памяти. Обратите внимание, что для длинных строк даже 64-битных int, которые я использовал здесь, будет недостаточно для хранения решения.

#define MAX_SIZE 1000
long long numFound[MAX_SIZE][MAX_SIZE]; //intermediate results, indexed by [startPosition][endPosition]

long long countPalindromes(const char *str) {
    int len = strlen(str);
    for (int startPos=0; startPos<=len; startPos++)
        for (int endPos=0; endPos<=len; endPos++)
            numFound[startPos][endPos] = 0;

    for (int spanSize=1; spanSize<=len; spanSize++) {
        for (int startPos=0; startPos<=len-spanSize; startPos++) {
            int endPos = startPos + spanSize;
            long long count = numFound[startPos+1][endPos];   //if str[startPos] is not in the palindrome, this will be the count
            char ch = str[startPos];

            //if str[startPos] is in the palindrome, choose a matching character for the palindrome end
            for (int searchPos=startPos; searchPos<endPos; searchPos++) {
                if (str[searchPos] == ch)
                    count += 1 + numFound[startPos+1][searchPos];
            }

            numFound[startPos][endPos] = count;
        }
    }
    return numFound[0][len];
}

Объяснение:

Массив numFound[startPos][endPos] будет содержать количество палиндромов, содержащихся в подстроке с индексами от startPos до endPos.

Мы перебираем все пары индексов (startPos, endPos), начиная с коротких интервалов и заканчивая более длинными. Для каждой такой пары есть два варианта:

1. Персонажа в str[startPos] нет на палиндроме. В этом случае существует numFound[startPos+1][endPos] возможных палиндромов - число, которое мы уже вычислили.

2. символ в str[startPos] находится в палиндроме (в его начале). Мы просматриваем строку, чтобы найти соответствующий символ, который нужно поместить в конец палиндрома. Для каждого такого символа мы используем уже вычисленные результаты в numFound, чтобы найти количество возможностей для внутреннего палиндрома.

ИЗМЕНИТЬ:

• Уточнение: когда я говорю «количество палиндромов, содержащихся в строке», это включает в себя несмежные подстроки. Например, палиндром «aba» содержится в «abca».

• Можно уменьшить использование памяти до O (n), воспользовавшись тем фактом, что для вычисления numFound[startPos][x] требуется только знание numFound[startPos+1][y] для всех y. Я не буду здесь этого делать, так как это немного усложняет код.

• Предварительная генерация списков индексов, содержащих каждую букву, может ускорить внутренний цикл, но в целом он все равно будет O (n ^ 3).

У меня есть способ сделать это за время O (N ^ 2) и пространство O (1), однако я думаю, что должны быть другие способы лучше.

основная идея заключалась в том, что длинный палиндром должен содержать маленькие палиндромы, поэтому мы ищем только минимальное совпадение, что означает два типа ситуаций: «аа», «аба». Если мы их нашли, разверните их и посмотрите, не является ли это частью длинного палиндрома.

    int count_palindromic_slices(const string &S) {
        int count = 0;

        for (int position=0; position<S.length(); position++) {
            int offset = 0;

            // Check the "aa" situation
            while((position-offset>=0) && (position+offset+1)<S.length() && (S.at(position-offset))==(S.at(position+offset+1))) {
                count ++;
                offset ++;
            }

            offset = 1;  // reset it for the odd length checking
            // Check the string for "aba" situation
            while((position-offset>=0) && position+offset<S.length() && (S.at(position-offset))==(S.at(position+offset))) {
                count ++;
                offset ++;
            }
        }
        return count;
    }

14 июня 2012 г. После некоторого расследования я считаю, что это лучший способ сделать это. быстрее принятого ответа.

Есть ли какой-нибудь пробег в выполнении начального обхода и построении индекса всех вхождений каждого символа.

 h = { 0, 2, 27}
 i = { 1, 30 }
 etc.

Теперь, работая слева, h, только возможные палидромы находятся в точках 3 и 17, есть ли у char [0 + 1] == char [3 -1] и т. Д. Палиндром. действительно ли char [0 + 1] == char [27 -1] нет, Дальнейший анализ char [0] не требуется.

Перейдите к char [1], нужно только, например, char [30 -1] и внутрь.

Затем, вероятно, можно поумнеть, когда вы определили палиндром, идущий из позиции x-> y, все внутренние подмножества являются известными палиндромами, поэтому мы имели дело с некоторыми элементами, можем исключить эти случаи из более позднего исследования.

Мое решение с использованием O(n) памяти и O(n^2) времени, где n - длина строки:

palindrome.c:

#include <stdio.h>
#include <string.h>

typedef unsigned long long ull;

ull countPalindromesHelper (const char* str, const size_t len, const size_t begin, const size_t end, const ull count) {
  if (begin <= 0 || end >= len) {
    return count;
  }
  const char pred = str [begin - 1];
  const char succ = str [end];
  if (pred == succ) {
    const ull newCount = count == 0 ? 1 : count * 2;
    return countPalindromesHelper (str, len, begin - 1, end + 1, newCount);
  }
  return count;
}

ull countPalindromes (const char* str) {
  ull count = 0;
  size_t len = strlen (str);
  size_t i;
  for (i = 0; i < len; ++i) {
    count += countPalindromesHelper (str, len, i, i, 0);  // even length palindromes
    count += countPalindromesHelper (str, len, i, i + 1, 1); // odd length palindromes
  }
  return count;
}

int main (int argc, char* argv[]) {
 if (argc < 2) {
  return 0;
 }
 const char* str = argv [1];
 ull count = countPalindromes (str);
 printf ("%llu\n", count);
 return 0;
}

Использование:

$ gcc palindrome.c -o palindrome
$ ./palindrome myteststring

РЕДАКТИРОВАТЬ: Я неправильно интерпретировал проблему как версию проблемы с непрерывной подстрокой. Теперь, учитывая, что кто-то хочет найти количество палиндромов для несмежной версии, я сильно подозреваю, что можно было бы просто использовать математическое уравнение для его решения, учитывая количество различных символов и их соответствующее количество символов.

Хммммм, думаю, я бы посчитал так:

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

Кажется, это именно то, что вы делаете, хотя я не уверен, что вы не учитываете дважды крайние случаи с повторяющимися символами.

Так что, по сути, я не могу придумать лучшего способа.

РЕДАКТИРОВАТЬ:
Подумав еще немного, это можно улучшить с помощью кеширования, потому что вы иногда подсчитываете палиндромы в одной и той же подстроке более одного раза. Итак, я полагаю, это демонстрирует, что определенно есть способ лучше.

Вот программа для поиска всех возможных палиндромов. в строке, написанной как на Java, так и на C ++.

Я не уверен, но вы можете попробовать Фурье. Эта проблема напомнила мне об этом: Алгоритм O (nlogn) - Найдите три одинаковых строки в двоичной строке

Только мои 2 цента