[字符串][Manacher][Hash] 2018ICPC 南京网络赛 I Skr

这个题当时tle到哭，心态爆炸，也几乎直接导致了没去看很简单的G，心情复杂。

这个判重刚好卡unordered_set，怎么都过不了，只能自己手写Hash判重。另外一个优化的点就是一定要边Manachar边计算，我一开始写的跑一遍Manacher之后枚举中点然后计算左右端点（那不就退化成n^2了嗯我当时就这么傻）。一边Manacher一边做，好处就是关于某个点对称的重复的回文串只会被算一次！这也是Manacher自身的算法决定的。。这个题其实出题人就是想让这么做的，不然要想计算所有出现的回文串的（不判重）MOD，应该是只能n^2吧。。（或许SAM可以？我没想过）。

需要巩固的地方：字符串Hash，字符串子串预处理（取模等），Manacher的原理的深刻理解。

丑陋的代码，后面打注释的是我当时脑子抽了写的n^2算法，哈哈

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=2e6+5;
const int MOD=1e9+7;


int len;
char ori[maxn];
char Ma[maxn<<1];
int Mp[maxn<<1];

/*
* abaaba
*     i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
* Ma[i]: $ # a # b # a # a # b # a #
* Mp[i]: 1 1 2 1 4 1 2 7 2 1 4 1 2 1
 */

const int MD=4000007;
int first[maxn<<1],nxt[maxn<<1],cnt=0;
ULL val[maxn<<1];
bool exist(ULL now)
{
    int u=now%MD;
    for(int i=first[u]; i; i=nxt[i])
        if(val[i]==now)
            return true;
    nxt[++cnt]=first[u];
    first[u]=cnt;
    val[cnt]=now;
    return false;
}

LL pten[maxn],sum[maxn];
ULL Hash[maxn],bas=10007,pw[maxn];
void calpre()
{
    pten[1]=1;
    pw[1]=bas;
    sum[1]=ori[0]-'0';
    Hash[1]=ori[0];
    for (int i=2; i<=len; i++)
    {
        pten[i]=10*pten[i-1]%MOD;
        pw[i]=pw[i-1]*bas;//no MOD
        sum[i]=sum[i-1]*10+ori[i-1]-'0';
        if(sum[i]>MOD)
            sum[i]%=MOD;
        Hash[i]=Hash[i-1]*bas+ori[i-1];//no -'0'
    }
}

ULL getHash(int l,int r)
{
    return Hash[r]-Hash[l-1]*pw[r-l+1];
}

LL solve(int l,int r)
{
    int L,R;
    L=(l>>1),R=(r>>1);
    ULL tmp=getHash(L,R);
    if(exist(tmp))
        return 0;
    else
    {
        LL ct=(sum[R]-sum[L-1]*pten[R-L+2]+MOD);
        if(ct>=MOD)
            ct%=MOD;
        return ct;
    }

}
int Manacher(char *s)
{
    int tl=(len<<1),L,R;
    ULL tmp;
    LL ans=0;

    int l=0;
    Ma[l++]='$';
    Ma[l++]='#';
    for (int i=0; ii?min(Mp[(id<<1)-i],mx-i):1;
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]])
        {
            if(Ma[i+Mp[i]]!='#')
                ans=(ans+solve(i-Mp[i],i+Mp[i]))%MOD;
            Mp[i]++;
        }
        if(i+Mp[i]>mx)
        {
            mx=i+Mp[i];
            id=i;
        }
    }
    return (ans%MOD+MOD)%MOD;
}

int main()
{
    gets(ori);
    len = strlen(ori);

    calpre();
    cout<>1)-(b>>1)+1;
            r=(i>>1)+(b>>1);
        }
        else
        {
            l=(i>>1)-(b>>1)+1;
            r=(i>>1)+(b>>1)-1;
        }
        //cout<MOD)
                ans%=MOD;
            //cout<

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

发表回复 取消回复

发表回复取消回复