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

Ответ 1

Сначала найдите все палиндромы в строке, так что L [i] [j] представляет длину j-го самого длинного палиндрома, который заканчивается на S [i]. Допустим, что S - входная строка. Это можно было бы сделать в O (N ^ 2) раз, сначала рассмотрев палиндром длины 1, затем длину 2 палиндрома и так далее. Поиск длины я палиндромов после того, как вы знаете всю длину палиндрома i-2, является вопросом сравнения одного символа.

Это проблема динамического программирования. Пусть A [i] представляет наименьшее число палиндромов, которые могут быть разложены подстрокой (S, 0, i-1).

A[i+1] = min_{0 <= j < length(L[i])} A[i - L[i][j]] + 1;

Изменить на основе запроса Micron: Вот идея зачета L [i] [j]. Я просто написал это, чтобы передать идею, у кода могут быть проблемы.

// Every single char is palindrome so L[i][0] = 1;
vector<vector<int> > L(S.length(), vector<int>(1,1));

for (i = 0; i < S.length(); i++) {
 for (j = 2; j < S.length; j++) {
   if (i - j + 1 >= 0 && S[i] == S[i-j + 1]) {
     // See if there was a palindrome of length j - 2 ending at S[i-1]
     bool inner_palindrome = false;
     if (j ==2) {
      inner_palindrome = true;
     } else {
       int k = L[i-1].length;
       if (L[i-1][k-1] == j-2 || (k >= 2 && L[i-1][k-2] == j-2)) {
         inner_palindrome = true;
       }
     }
     if (inner_palindrome) {
       L[i].push_back(j);
     }
   } 
 }
} 

Ответ 2

Вы можете сделать это в O (n ^ 2) раз, используя отпечаток пальца Rabin-Karp, чтобы предварительно обработать строку, чтобы найти все палиндромы в O (n ^ 2) времени. После предварительной обработки вы запускаете код, похожий на следующий:

np(string s) {
  int a[s.size() + 1];
  a[s.size()] = 0;
  for (int i = s.size() - 1; i >= 0; i--) {
    a[i] = s.size() - i;
    for (int j = i + 1; j <= s.size(); j++) {
      if (is_palindrome(substr(s, i, j))) // test costs O(1) after preprocessing
        a[i] = min(a[i], 1 + a[j]);
  }
  return a[0];
}

Ответ 3

Эквивалентная проблема заключается в вычислении числа Snip строки.

Предположим, вы хотели вырезать строку, используя наименьшее количество срезов, так что каждая оставшаяся часть была сама палиндром. Количество таких сокращений мы будем называть Snip Number строки. Это номер snip всегда равен одному меньшему, чем наименьшее количество палиндромов в данной строке. Каждая строка длины n имеет число snip не более n-1, и каждый палиндром имеет номер snip 0. Здесь работает код python.

def snip_number(str):
    n=len(str)
 
 #initialize Opt Table
 # Opt[i,j] = min number of snips in the substring str[i...j]
 
    Opt=[[0 for i in range(n)] for j in range(n) ]
 
 #Opt of single char is 0
    for i in range(n):
     Opt[i][i] = 0
 
 #Opt for adjacent chars is 1 if different, 0 otherwise
    for i in range(n-1):
     Opt[i][i+1]= 1 if str[i]!=str[i+1] else 0
 
 
# we now define sil as (s)substring (i)interval (l) length of the
# interval [i,j] --- sil=(j-i +1) and j = i+sil-1
 
# we compute Opt table entry for each sil length and
# starting index i
 
    for sil in range(3, n+1):
     for i in range(n-sil+1):
       j = i+sil-1
       if (str[i] == str[j] and Opt[i+1][j-1]==0):
         Opt[i][j] = 0
       else:
         snip= min( [(Opt[i][t]+ Opt[t+1][j] + 1 ) for t in range(i,j-1)])
         Opt[i][j] = snip

    return Opt[0][len(str)-1]
#end function snip_number()
mystr=[""for i in range(4)]         
mystr[0]="abc"
mystr[1]="ohiho"
mystr[2]="cabacdbabdc"
mystr[3]="amanaplanacanalpanama aibohphobia "


for i in range(4):
     print mystr[i], "has snip number:", snip_number(mystr[i])
     
# abc has snip number: 2
# ohiho has snip number: 0
# cabacdbabdc has snip number: 2
# amanaplanacanalpanama aibohphobia  has snip number: 1

Ответ 4

bool ispalindrome(string inp)
{
    if(inp == "" || inp.length() == 1)
    {
        return true;
    }
    string rev = inp;

    reverse(rev.begin(), rev.end());

    return (rev == inp);
}

int minsplit_count(string inp)
{
    if(ispalindrome(inp))
    {
        return 0;
    }

    int count= inp.length();

    for(int i = 1; i < inp.length(); i++)
    {
        count = min(count, 
                      minsplit_count(inp.substr(0, i))              + 
                      minsplit_count(inp.substr(i, inp.size() - i)) + 
                      1);
    }

    return count;
}

Ответ 5

O (n ^ 3). Итерируйте строку рекурсивно. Для каждой буквы установите каждый палиндром с этим письмом как начало палиндрома. Обратите внимание на нечетные и четные палиндромы. Повторяйте до конца строки. Если в конце строки количество палиндрома минимально, помните, как вы туда попали. Не итерации, если сумма текущих палиндромов подсчитывается, а оставшиеся буквы в строке больше, чем текущий счетчик палиндрома.

Оптимизация: при открытии палиндромов начинается с конца строки и выполняется поиск текущей буквы. Проверьте подстроку на "palindromness". Не начинайте с кратчайших палиндромов, это не оптимально.