Extend to Palindrome UVA - 11475（补成回文串）

题意：

　　就是用最少的字符把原字符串补成回文串

解析：

　　emm/。。。/网上都是用kmp和后缀数组做的 我没想到这俩的思路。。。emmm。。。

想到了exkmp的  就是原串和逆串匹配一下  注意要保证这个匹配的最大长度 要到原串的结尾

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <cctype>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define rep(i, a, n) for(int i=a; i<n; i++)

#define lap(i, a, n) for(int i=n; i>=a; i--)

#define lep(i, a, n) for(int i=n; i>a; i--)

#define rd(a) scanf("%d", &a)

#define rlld(a) scanf("%lld", &a)

#define rc(a) scanf("%c", &a)

#define rs(a) scanf("%s", a)

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int nex[maxn], ex[maxn];

char s1[maxn], s2[maxn];

void get_next(char *s)

{

    int i=, j, po, len = strlen(s);

    nex[] = len;

    while(s[i] == s[i+] && i+ < len)

        i++;

    nex[] = i;

    po = ;

    for(int i=; i<len; i++)

    {

        if(i+nex[i-po] < po + nex[po])

            nex[i] = nex[i-po];

        else

        {

            j = po + nex[po] - i;

            if(j < ) j = ;

            while(i + j < len && s[i+j] == s[j])

                j++;

            nex[i] = j;

            po = i;

        }

    }

}

void get_ex(char *s1, char *s2)

{

    int i=, j, po, len1 = strlen(s1), len2 = strlen(s2);

    get_next(s2);

    while(s1[i] == s2[i] && i < len1 && i < len2)

        i++;

    ex[] = i;

    po = ;

    for(int i=; i<len1; i++)

    {

        if(i + nex[i - po] < po + ex[po])

            ex[i] = nex[i-po];

        else

        {

            j = po + ex[po] - i;

            if(j < ) j = ;

            while(i + j < len1 && j < len2 && s1[i+j] == s2[j])

                j++;

            ex[i] = j;

            po = i;

        }

    }

}

int main()

{

    while(~scanf("%s", s1))

    {

        int len = strlen(s1);

        strcpy(s2, s1);

        reverse(s2, s2+len);

        get_next(s2);

        get_ex(s1, s2);

        if(ex[] == len)

        {

            cout<< s1 <<endl;

            continue;

        }

        int maxx = -INF, id;

        for(int i=; i<len; i++)

            if(maxx < ex[i] && i + ex[i] == len)

            {

                maxx = ex[i];

                id = i;

            }

     //   cout<< maxx <<endl;

        if(maxx == )

        {

            cout<< s1;

            cout<< s2+ <<endl;

            continue;

        }

        cout<< s1;

        for(int i=id-; i>=; i--)

            cout<<s1[i];

        cout<<endl;

    }

    return ;

}

Extend to Palindrome UVA - 11475（补成回文串）的相关教程结束。