HDU - 3294 Girls' research(manacher)

素颜马尾好姑娘i 2022-06-04 02:59 158阅读 0赞

[点我看题][Link 1]

题意：给一个字符和一个串，根据一定的规则变换串，然后找出最长回文子串并输出串最右两端的下标。

分析：manacher模板题，在求解下标的时候利用到manacher最基本的性质—变换后的字符串的回文子串都是奇数，然后可以很顺利的找出manacher的下标。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define INF 0x3f3f3f3f
    const int maxn = 2e5+100;
    int n;
    char ch;
    char s[maxn<<1];
    int p[maxn<<1];
    
    void manacher()
    {
        memset(p,0,sizeof(p));
        for( int i = n; i >= 0; i--)
        {
            s[i*2+2] = s[i];
            s[i*2+1] = '#';
        }
        s[0] = '$';
    
        int id, mx = 0;
        for( int i = 1; i < 2*n+1; i++)
        {
            if( i < mx)
                p[i] = min(p[2*id-i],mx-i);
            else
                p[i] = 0;
            while( s[i-p[i]] == s[i+p[i]])
                p[i]++;
            if( i+p[i] > mx)
            {
                mx = i+p[i];
                id = i;
            }
        }
    }
    
    int main()
    {
        while( ~scanf("%c%s",&ch,s))
        {
            n = strlen(s);
            int d = ch-'a';
            for( int i = 0; i < n; i++)
                s[i] = (s[i]-'a'-d+26)%26+'a';
    
            manacher();
            int id = -1, mx = -INF;
            for( int i = 1; i < 2*n+1; i++)
                if( p[i] > mx)
                    mx = p[i], id = i;
    
            mx--;
            int tmp = mx/2;//前面或后面有多少个字母在回文中
            if( tmp)
            {
                int l = id-mx+1;
                int r = id+mx-1;
                printf("%d %d\n",(l-2)/2,(r-2)/2);
                for( int i = l; i <= r; i++)
                    if( s[i] != '#')
                        printf("%c",s[i]);
                puts("");
            }
            else
                puts("No solution!");
    
            getchar();
        }
    
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3294