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

Я отправляю это от имени друга, так как считаю, что это довольно интересно:

Возьмите строку "abb". Оставляя любое количество букв меньше, чем длина строки в итоге получается 7 строки.

a b b ab ab bb abb

Из этих 4 являются палиндромы.

Аналогично для строки

"hihellolookhavealookatthispalindromexxqwertyuiopasdfghjklzxcvbnmmnbvcxzlkjhgfdsapoiuytrewqxxsoundsfamiliardoesit"

(длина строки 112) 2 ^ 112 - 1 могут быть сформированы строки.

Из них сколько палиндромы??

Ниже его реализация (в С++, C тоже хорошо). Это довольно медленно с очень длинными словами; он хочет знать, для чего самый быстрый алгоритм для этого (и мне тоже интересно: D).

#include <iostream>
#include <cstring>

using namespace std;



void find_palindrome(const char* str, const char* max, long& count)
{
    for(const char* begin = str; begin < max; begin++) {
        count++;
        const char* end = strchr(begin + 1, *begin);
        while(end != NULL) {
            count++;
            find_palindrome(begin + 1, end, count);
            end = strchr(end + 1, *begin);
        }
    }
}


int main(int argc, char *argv[])
{
    const char* s = "hihellolookhavealookatthis";
    long count = 0;

    find_palindrome(s, strlen(s) + s, count);

    cout << count << endl;
}

Ответ 1

Прежде всего, у вашего друга-решения есть ошибка, так как 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), начиная с коротких интервалов и переходя к более длинным. Для каждой такой пары существует два варианта:

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

ИЗМЕНИТЬ

Уточнение: когда я говорю "количество палиндромов, содержащихся в строке", это включает несмежные подстроки. Например, палиндром "aba" содержится в "abca".
Можно сократить использование памяти до O (n), воспользовавшись тем, что для вычисления numFound[startPos][x] требуется знание numFound[startPos+1][y] для всех y. Я не буду делать это здесь, так как это немного усложняет код.
Прегенерирующие списки индексов, содержащих каждую букву, могут сделать внутренний цикл быстрее, но он все равно будет O (n ^ 3) в целом.

Ответ 2

У меня есть способ сделать это в 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 г. После некоторого расследования я считаю, что это лучший способ сделать это. быстрее, чем принятый ответ.

Ответ 3

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

 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, все внутренние подмножества являются известными палиндромами, поэтому мы имеем дело с некоторыми предметами, может устранить эти случаи из более позднего экзамена.

Ответ 4

Мое решение с использованием 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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

Ответ 7

int main()
 {
    string palindrome;

    cout << "Enter a String to check if it is a Palindrome";

    cin >> palindrome;

    int length = palindrome.length();

    cout << "the length of the string is " << length << endl;

    int end = length - 1;
    int start = 0;
    int check=1;

    while (end >= start) {
        if (palindrome[start] != palindrome[end]) {
            cout << "The string is not a palindrome";
            check=0;
            break;
        }
        else
        {
            start++;
            end--;

        }

    }
    if(check)
    cout << "The string is a Palindrome" << endl;

}

Ответ 8

public String[] findPalindromes(String source) {

    Set<String> palindromes = new HashSet<String>();        
    int count = 0;
    for(int i=0; i<source.length()-1; i++) {            
        for(int j= i+1; j<source.length(); j++) {               
            String palindromeCandidate = new String(source.substring(i, j+1));
            if(isPalindrome(palindromeCandidate)) {
                palindromes.add(palindromeCandidate);                   
            }
        }
    }

    return palindromes.toArray(new String[palindromes.size()]);     
}

private boolean isPalindrome(String source) {

    int i =0;
    int k = source.length()-1;      
    for(i=0; i<source.length()/2; i++) {            
        if(source.charAt(i) != source.charAt(k)) {
            return false;
        }
        k--;
    }       
    return true;
}

Ответ 9

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

Только мои 2cents