UVA – 11475 Extend to Palindrome manacher+贪心

ProLightsfx 2017-1-18 138 1/18

E - Extend to Palindrome manacher+贪心 

 Source

UVA - 11475

My Solution

题意:给出一个字符串,在末尾添加尽可能少的字符串,使这个新字符串为回文串,输出新字符串。

manacher+贪心

先用manacher O(n)的跑出原字符串的以每个i为中心的回文子串,

然后应该自己得出的一个manacher的结论if(len[i + j] >= (j - i)/2 + 1) 则字符串s[i......j]为回文子串。

也就是从原串的右边开始,向左跑,找到以sz-1为右端点的最大回文子串,标记为ans开始,则输出原串后,从ans-1开始到0按照顺序每个字符依次输出。

复杂度 O(n)

 

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

int len[2*maxn];
char str[maxn];

void manacher(int n)
{
    int p, q, r;
    len[0] = 1;
    for(int i = 1, j = 0; i < (n << 1) - 1; i++){ p = i >> 1, q = i - p, r = ((j + 1) >> 1) + len[j] - 1;
        len[i] = r < q ? 0 : min(r - q + 1, len[(j << 1) - i]); while(p > len[i] - 1 && q + len[i] < n && str[p - len[i]] == str[q + len[i]]) len[i]++; if(q + len[i] - 1 > r)
            j = i;
    }
}


int main()
{
    #ifdef LOCAL
    freopen("e.txt", "r", stdin);
    //freopen("e.out", "w", stdout);
    #endif // LOCAL
    int sz, i, j, ans;
    while(scanf("%s", str) != EOF){
        sz = strlen(str); ans = sz - 1;
        manacher(sz);
        for(i = sz - 2, j = sz - 1; i >= 0; i--){
            if(len[i + j] >= (j - i)/2 + 1){
                ans = i;
            }
        }
        printf("%s", str);
        for(i = ans - 1; i >= 0; i--) putchar(str[i]);
        putchar('n');
    }
    return 0;
}

 


非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx

- THE END -

ProLightsfx

11月15日19:51

最后修改:2024年11月15日
0

非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

共有 0 条评论