Petrozavodsk Winter-2013. Ural FU Contest Problem D. Five Palindromes manacher、一个串切割成5个回文子串、优化

Problem D. Five Palindromes manacher、一个串切割成5个回文子串、优化
Source

Petrozavodsk Winter-2013. Ural FU Contest

My Solution

manacher、一个串切割成5个回文子串、优化

第一次使用manacher 嘿嘿☺☺

为了方便处理奇偶的情况， 我们把 区间 [ i , j ] 的回文子串半径保存在 len[ i + j ] 里，

if(len[ i + j ] >= (j - i)/2 + 1) 则[ i , j ] 为回文串

可以O(n)的处理出len 所有中心的回文子串长度

这里先跑一边 manacher(n) 得到 len[]数组

然后O(n) 的预处理出 第一个字符串的右端点 i，放在一个队列里

并且O(n) 的预处理出 最后一个字符串的左端点 j，放在一个vector里

对于每一个 i， 把所有 (i < j)的j跑一遍

并且判断[ i+1, j -1 ] 是否有回文子串 [ i + 1, k ],  [ k + 1, u ],  [ u + 1, j - 1 ] 如果满足条件则输出并且用 return 0; 或者 exit(0)直接结束程序

否则跑完所有情况都没有符合要求的答案则 "NO"

复杂度 不知道怎么算 大概 nlogn的， 如果不预处理出那些东西最糟糕的复杂度可能 O(n^2) TLE 23，预处理后大概最好的情况 O(n)， 最差的情况O(nlogn)左右

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

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

inline 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;
    }
}

queue que;
vector vec;


int main()
{

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #ifdef LOCAL
    int T = 3;
    while(T--){
    #endif // LOCAL
    scanf("%s", str);
    int n = strlen(str);
    manacher(n);
    //for(int i = 0; i < 2*n; i++)
    //cout<<str<<endl;
    for(int i = 0; i < n; i++){ if(i == 0 || len[0 + i] >= (i - 0) / 2 + 1){que.push(i);}
    }
    for(int i = n-1; i >= 0; i--){
        if(i == n - 1 || len[n - 1 + i] >= (n - 1 - i) / 2 + 1){vec.push_back(i);}
    }

    int szv = vec.size(), i, j;

    while(!que.empty()){
        i = que.front();
        que.pop();
        for(int x = 0; x < szv; x++){
            j = vec[x];
            if(j <= i) break;
    //!
            for(int k = i + 1; k < j; k++){ if(k == i + 1 || len[i + 1 + k] >= (k - (i+1)) / 2 + 1){
                    for(int u = k + 1; u < n; u++){ if(u == k + 1 || len[k + 1 + u] >= (u - (k+1)) / 2 + 1){
                            if(len[u + 1 + j - 1] >= (j - 1 - (u + 1)) / 2 + 1){
                                printf("YESn");
                                for(int v = 0; v < n; v++){
                                    putchar(str[v]);
                                    if(v == i || v == j-1 || v == k || v == u) putchar('n');
                                }
                                putchar('n');
                                return 0;
                            }
                        }
                        //else break;
                    }
                }
                //else break;
            }

        }
        //else break;

    }
    printf("NOn");

    #ifdef LOCAL
    vec.clear();
    printf("n");
    }
    #endif // LOCAL
    return 0;
}