Минимальное количество символов, вставляемых в конец строки, чтобы сделать ее палиндромом

Question

Минимальное количество символов, вставляемых в конец строки, чтобы сделать ее палиндромом

Вопрос вот в чем--

Мы должны найти минимальное количество символов, которые будут вставлены в конец строки, чтобы сделать ее палиндромом.

Поэтому, пытаясь решить эту задачу, я решил, что это эквивалентно нахождению самой большой палиндромной подстроки, которая также является суффиксом строки.

Я мог бы сделать это в O(n^2) легко, но я ищу решение O(n), которое, вероятно, возможно с помощью модифицированного KMP. Кто-нибудь, пожалуйста, помогите мне понять из.

721 2

algorithm data-structures

2 ответов:

Comments

Ничего не найдено.

IVlad · Accepted Answer · 2017-05-23 15:08:40

У меня есть подход, который использует хэширование, размещенное в качестве ответа здесь.

Вы действительно можете также использовать KMP. Вы можете вычислить префиксную функцию Для обратной строки, а затем повторить начальную строку слева направо:

KMP вычисляет функцию prefix[i] = longest prefix of the string that is a suffix of string[1..i]
Тем не менее, мы хотим знать the longest suffix of our string that is a prefix of the reversed string. Почему? Если мы имеем:
15232 => reverse = 23251
Тогда самый длинный суффикс строки, являющейся префиксом перевернутой строки, - 232. Это палиндром, и он позволяет нам найти то, что вы спрашиваете, потому что суффикс строки перекрывает префикс перевернутой строки, если эти два являются палиндромами.

У вас есть случаи:
prefix[i] = length - i => you can get a palindrome of 
            length 2*prefix[i] centered at i and i+1

prefix[i] = length - i + 1 => you can get a palindrome of
            length 2*prefix[i] - 1 centered at i

prefix[i] < length - i => you can't have a palindrome, ignore this position
, Так что достаточно для вычисления префикс-функции алгоритма КМП.

Rajat Singhal · Accepted Answer · 2017-08-06 10:02:13

Простой код для вставки минимального количества символов и их возврата, чтобы сделать данную строку паллиндромом

#include <bits/stdc++.h>
using namespace std;
bool isPalin(char *s,int x,int l)
{
    for(int i=x,j=l-1;i<j;i++,j--)
        if(s[i]!=s[j])
            return 0;
    return 1;
}
char * f(char *s)
{
    // if s is NULL return NULL
    if(!s)
        return NULL;
    int i,l,j;
    l=strlen(s);
    for(i=0;i<l;i++)
    {
        // check if string is pallindrome from [i...l-1]
        if(isPalin(s,i,l) == 1)
            break;
    }
    // if s is already a pallindrome return NULL
    if(i==0)
        return NULL;
    int k=0;
    // make a char*
    char *ans = new char[i+1];
    for(i-=1;i>=0;i--)
        ans[k++]=s[i];
    ans[k++]='\0';
    return ans;
}

int main() {
    char *a = "wxytabbat";
    cout<<f(a)<<"\n";
    return 0;
}