UESTC 1066 Palindromic String manacher

ProLightsfx 2017-7-18 203 7/18

Palindromic String manacher

Source

2015 UESTC Training for Search Algorithm and String

UESTC 1066 Palindromic String

My Solution

题意:求出前缀的回文重数的和,(回文重数是递归定义的,详见题面)。

manacher
先用manacher跑出所有的回文子串,并把[i,j]的回文子串半径大小存储在了len[i+j]里,
然后从做到右跑一遍,且同时用f[i]表示0~i的回文子串重数,
每次
if(f[(i+1)/2-1] && len[i] >= i/2+1){
f[i] = f[(i+1)/2-1] + 1;
ans += f[i];
}
else if(len[i] >= i/2+1){
f[i] = 1;
ans += f[i];
}
时间复杂度 O(n)
空间复杂度 O(n)

 

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 2e6 + 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 f[MAXN];

int main()
{
    #ifdef LOCAL
    freopen("e.txt", "r", stdin);
    //freopen("e.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);


    scanf("%s", str);
    int sz = strlen(str), i;
    LL ans = 1;
    manacher(sz);
    f[0] = 1;
    for(i = 1; i < sz; i++){
        //cout << 0 << " "<< i << " " << len[i] << endl; if(f[(i+1)/2-1] && len[i] >= i/2+1){
            f[i] = f[(i+1)/2-1] + 1;
            ans += f[i];
        }
        else if(len[i] >= i/2+1){
            f[i] = 1;
            ans += f[i];
        }
    }
    printf("%lldn", ans);



    #ifdef LOCAL
    memset(len, 0, sizeof len);
    memset(f, 0, sizeof f);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

 


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

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx

- THE END -

ProLightsfx

11月15日12:38

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

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

共有 0 条评论