马拉车manacher

目的：线性查找一个串的最长回文子串

时间复杂度：O(n)

len[i]表示以i为中心的回文串的半径，mx即为当前计算回文串最右边字符的最大值，p是中心点mid，mx-i和2*p-1关于p对称

https://blog.csdn.net/csdn_kou/article/details/82917937

hdu3068，板子题，求最长回文长度。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int t,len[maxn*];

char S[maxn*],T[maxn*],s[maxn*];

int init(char *str)

{

    int n=strlen(str);

    for(int i=,j=;i<=*n;j++,i+=)

    {

        s[i]='#';

        s[i+]=str[j];

    }

    s[]='$';

    s[*n+]='#';

    s[*n+]='@';

    s[*n+]='\n';

    return *n+;

}

void manacher(int n)

{

    int mx=,p=;

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

    {

        if(mx>i)len[i]=min(mx-i,len[*p-i]);

        else len[i]=;

        while(s[i-len[i]]==s[i+len[i]])len[i]++;

        if(len[i]+i>mx)mx=len[i]+i,p=i;

    }

}

int main()

{

    while(scanf("%s",S)!=EOF)

    {

        int Len=strlen(S),n=init(S);

        for(int i=;i<=n;i++)len[i]=;

        manacher(n);

        int ans=;

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

        {

            ans=max(ans,len[i]-);

        }

        printf("%d\n",ans);

    }

    return ;

}

2019徐州G colorful string，求所有回文子串的value之和，一个串的value为串中字母种类，dfs预处理了第i位前一个a-z的位置，复杂度26*n。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=3e5+;

int t,len[maxn*];

char S[maxn*],T[maxn*],s[maxn*];

int init(char *str){

    int n=strlen(str);

    for(int i=,j=;i<=*n;j++,i+=){

        s[i]='#';

        s[i+]=str[j];

    }

    s[]='$';

    s[*n+]='#';

    s[*n+]='@';

    s[*n+]='\n';

    return *n+;

}

void manacher(int n)

{

    int mx=,p=;

    for(int i=;i<=n;i++){

        if(mx>i) len[i]=min(mx-i,len[*p-i]);

        else len[i]=;

        while(s[i-len[i]]==s[i+len[i]]) len[i]++;

        if(len[i]+i>mx) mx=len[i]+i,p=i;

    }

}

int dp[maxn*][],place[];

int main()

{

    scanf("%s",S);

    int Len=strlen(S),n=init(S);

    for(int i=;i<=n;i++)len[i]=;

    manacher(n);

    ll ans=;

    int k=;

    for(int i=;i<;i++)place[i]=-;

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

    {

        if(i%==)place[S[k++]-'a']=i;

        for(int j=;j<;j++)dp[i][j]=place[j];

    }

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

    {

        for(int j=;j<;j++)

        {

            if(i-dp[i][j]<len[i])

            {

                ans+=1ll*(len[i]-(i-dp[i][j]))/;

            }

        }

    }

    printf("%lld\n",ans);

    return ;

}

hdu3613，一个串割成两个串，如果是回文串则val为所有字母val之和，否则为零。

字母的val题目给出，求使总串的val最高的割法的val值。

#include<bits/stdc++.h>

using namespace std;

const int maxn=5e5+;

int t,len[maxn<<];

char S[maxn<<],T[maxn<<],s[maxn<<];

int init(char *str)

{

    int n=strlen(str);

    for(int i=,j=;i<=*n;j++,i+=)

    {

        s[i]='#';

        s[i+]=str[j];

    }

    s[]='$';

    s[*n+]='#';

    s[*n+]='@';

    s[*n+]='\n';

    return *n+;

}

void manacher(int n)

{

    int mx=,p=;

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

    {

        if(mx>i)len[i]=min(mx-i,len[*p-i]);

        else len[i]=;

        while(s[i-len[i]]==s[i+len[i]])len[i]++;

        if(len[i]+i>mx)mx=len[i]+i,p=i;

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int val[]={};

        for(int i=;i<;i++)scanf("%d",&val[i]);

        cin>>S;

        int Len=strlen(S),n=init(S);

        for(int i=;i<=n;i++)len[i]=;

        manacher(n);

        int lg=,rg=,ans=;

        for(int i=;i<Len;i++)rg+=val[S[i]-'a'];

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

        {

            if(i%==)

            {

                lg+=val[s[i]-'a'];

                rg-=val[s[i]-'a'];

            }

            else

            {

                int l=,r=*Len+,tmplg=,tmprg=;

                if(i!=l&&i!=r)

                {

                    int mid1=(l+i)>>,mid2=(i+r)>>;

                    if(len[mid1]==mid1-l+)tmplg=lg;

                    if(len[mid2]==r-mid2+)tmprg=rg;

                    ans=max(ans,tmplg+tmprg);

                }

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

hdu3294，求最早出现的最长回文串的l、r区间，并且转换后输出

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+;

int t,len[maxn<<];

char S[maxn<<],T[maxn<<],s[maxn<<];

int init(char *str)

{

    int n=strlen(str);

    for(int i=,j=;i<=*n;j++,i+=)

    {

        s[i]='#';

        s[i+]=str[j];

    }

    s[]='$';

    s[*n+]='#';

    s[*n+]='@';

    s[*n+]='\n';

    return *n+;

}

void manacher(int n)

{

    int mx=,p=;

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

    {

        if(mx>i)len[i]=min(mx-i,len[*p-i]);

        else len[i]=;

        while(s[i-len[i]]==s[i+len[i]])len[i]++;

        if(len[i]+i>mx)mx=len[i]+i,p=i;

    }

}

int main()

{

    char ch;

    while(scanf("%c %s",&ch,S)!=EOF)

    {

        int Len=strlen(S),n=init(S);

        for(int i=;i<=n;i++)len[i]=;

        manacher(n);

        int ans=,l=,r=;

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

        {

            if(len[i]->ans)

            {

                ans=len[i]-;

                l=(i-len[i]+)/;

                r=(i+len[i]-)/;

            }

        }

        if(ans<)printf("No solution!\n");

        else

        {

            printf("%d %d\n",l,r);

            for(int i=l;i<=r;i++)

            {

                S[i]=S[i]-ch+'a';

                if(S[i]>'z')S[i]=S[i]-'z'+'a'-;

                if(S[i]<'a')S[i]=S[i]+'z'-'a'+;

            }

            S[r+]='\0';

            printf("%s\n",S+l);

        }

        getchar();

    }

    return ;

}

hdu4513，最长递增(不降)回文串，manacher里只需要改个while

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+;

int t,len[maxn*];

int s[maxn*],T[maxn*],S[maxn*];

int init(int *str,int n)

{

    for(int i=,j=;i<=*n;j++,i+=)

    {

        s[i]=-;

        s[i+]=str[j];

    }

    s[]=-;

    s[*n+]=-;

    s[*n+]=-;

    return *n+;

}

void manacher(int n)

{

    int mx=,p=;

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

    {

        if(mx>i)len[i]=min(mx-i,len[*p-i]);

        else len[i]=;

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

        if(len[i]+i>mx)mx=len[i]+i,p=i;

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n;

        scanf("%d",&n);

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

        scanf("%d",&S[i]);

        int Len=n,len2=init(S,n);

        for(int i=;i<=n;i++)len[i]=;

        manacher(len2);

        int ans=;

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

        {

            ans=max(ans,len[i]-);

        }

        printf("%d\n",ans);

    }

    return ;

}

...

巴特西

马拉车manacher

最新文章

热门文章