P3449 [POI2006]PAL-Palindromes 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 还没有评论
作者: SovietPower✨ 更新时间: 2017-08-08 20:52  在Ta的博客查看 举报    2  

//学的不久,仅个人理解,可能不对,有错请指出

若要两个回文串相连后仍是回文串,那回文串 si一定是 sj(leni<=lenj)的循环节(可以相等,每个回文串自己+自己肯定是个回文串)

是循环节也就是是前缀

先用Trie树得出一个串上每个点的前缀情况,再通过Hash判断是否为其循环节

这样得出所有 len[i]<=len[j]的满足条件的(si,sj),同样也有(sj,si)

so 答案再*2 ,但是每个(i,i)仅有一个,这样有n个在res*2时多了n,so res = res*2-n

另对于Hash判断循环节,若i是j的循环节,满足:

Hash[i]* p^len[j]+Hash[j] == Hash[j]* p^len[i]+Hash[i]

设字串i为abc,母串j为abcabc,选的Hash进制为p

Hashi = ((0+a)p+b)p+c = ap2+bp+c (数字均为次数)

Hashj = (((((0+a)p+b)p+c)p+a)p+b)p+c = ap5+bp4+cp3+ap2+bp+c

现令 x = Hash[i]* Base^len[j] + Hash[j] = I*p^6 + J

y = Hash[j]* Base^len[i] + Hash[i] = J*p^3 + I

可得 x = y = ap8+bp7+cp6+ap5+bp4+cp3+ap2+bp+c

(一推就出)

非指针版 817ms 290640kb 内存比较。。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2000005,base=233;
typedef unsigned long long ull;

int n,len[N],t[N][27],sz,val[N],belong[N];
//belong[i]:i这个节点属于哪个串的 
//注意总长不会超过N,即节点数也不会超过N 
//val[N*27] 过大导致一直RE。。 
ull p[N],Hash[N];
string s[N];
char tmp[N];

inline int read()
{
    int now=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())
      if(c=='-') f=-1;
    for(;isdigit(c);c=getchar())
      now=(now<<3)+(now<<1)+c-'0';
    return now*f;
}

void Pre()
{
    p[0]=1;
    for(int i=1;i<=2000000;++i)
        p[i]=p[i-1]*base;
}

int main()
{
    Pre();
    n=read();
    for(int i=1;i<=n;++i)
    {
        len[i]=read();
        scanf("%s",tmp);s[i]=tmp;//这样读string会快 
//    TLE:cin>>tmp;
        int u=0;
        ull v=0;
        for(int j=0;j<len[i];++j)
        {
            int id=s[i][j]-'a';
            if(!t[u][id])
                t[u][id]=++sz;
            u=t[u][id];
            v=v*base+(ull)(id+1);
        }
        ++val[u],belong[u]=i,Hash[i]=v;
    }
    long long res=0;
    for(int i=1;i<=n;++i)
    {
        int u=0;
        for(int j=0;j<len[i];++j)
        {
            u=t[u][s[i][j]-'a'];
            if(val[u] && Hash[belong[u]]*p[len[i]]+Hash[i]==Hash[i]*p[len[belong[u]]]+Hash[belong[u]])
                res+=val[u];
        }
    }
    printf("%lld",res*2-n);

    return 0;
}

指针版 优化内存 941ms 101609kb

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2000005,base=233;
typedef unsigned long long ull;

int n,len[N];
struct Node
{
    int val,belong;
    Node *nxt[27];
    Node()
    {
        val=0;memset(nxt,NULL,sizeof nxt);
    }
};
Node *root=new Node();
Node *rt;
ull p[N],Hash[N];
string s[N];
char tmp[N];

inline int read()
{
    int now=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())
      if(c=='-') f=-1;
    for(;isdigit(c);c=getchar())
      now=(now<<3)+(now<<1)+c-'0';
    return now*f;
}

void Pre()
{
    p[0]=1;
    for(int i=1;i<=2000000;++i)
        p[i]=p[i-1]*base;
}

int main()
{
    Pre();
    n=read();
    for(int i=1;i<=n;++i)
    {
        len[i]=read();
        scanf("%s",tmp);s[i]=tmp;//这样读string会快 
//    TLE:cin>>tmp;
        rt=root;
        ull v=0;
        for(int j=0;j<len[i];++j)
        {
            int id=s[i][j]-'a';
            if(rt->nxt[id]==NULL)
                rt->nxt[id]=new Node();
            rt=rt->nxt[id];
            v=v*base+(ull)(id+1);
        }
        ++rt->val,rt->belong=i,Hash[i]=v;
    }
    long long res=0;
    for(int i=1;i<=n;++i)
    {
        rt=root;
        for(int j=0;j<len[i];++j)
        {
            rt=rt->nxt[s[i][j]-'a'];
            if(rt->val && Hash[rt->belong]*p[len[i]]+Hash[i]==Hash[i]*p[len[rt->belong]]+Hash[rt->belong])
                res+=rt->val;
        }
    }
    printf("%lld",res*2-n);

    return 0;
}

评论

  • 还没有评论
作者: 面毕者 更新时间: 2019-06-24 17:55  在Ta的博客查看 举报    0  

【题解】[POI2006]PAL-Palindromes


思路:

  • 回文串和自己相加仍是回文串。

  • 当$S[i]$是$S[j]$的前缀时,$S[i]+S[j]$可能构成回文串。

  • 对于$S[i]​$,利用$Trie​$获得是$S[i]​$的前缀的字符串。再利用字符串的$Hash​$判断是否回文。

  • 知道前串的长度、两串的散列值,就可以获得两串连接后的散列值。如下:

    • HashLink = HashValue[Left] * HashPow[Right.Length] + HashValue[Left]

下面是部分代码(头文件省略)。

  • 把字符串加入字典树,并且计算$Hash$值和长度。
int Add (int From ) {
    int P = 0 ,R = 1 ;
    unsigned long long int NowHash = 0 , NowLen = 0;
    for (int i = From ; S[i] != '0' ; ++ i) {
        if (!T[P][S[i] - 'a']) T[P][S[i] - 'a'] = ++ Tot;
        P = T[P][S[i] - 'a'] ;
        ++ R;
        NowHash = NowHash * HashBase + S[i] ;
        ++ NowLen ;
    }
    ++ End[P] ;
    Len[P] = NowLen , HashValue[P] = NowHash ;
    return From + R ;
}
  • 对于每一个字符串,枚举它的前缀,并且判断$Hash(Left + Right) == Hash(Right + Left)$。如果成立,那将对答案贡献2。

    • void Ask (int P , int Now , int E ) {
      
      if (Now > E) {
          NowP = P ;
          return ;
      }
      Ask (T[P][S[Now] - 'a'] , Now + 1 , E ) ;
      
      if (End[P]) {
          if (HashValue[NowP] * HashPow[Len[P]] + HashValue[P] == HashValue[P] * HashPow[Len[NowP]] + HashValue[NowP]) {
              Ans += 2 ;
              if (P == NowP) -- Ans ;
          }
      }
      }
  • 最后,每个字符串和自己可以连接。

  • 完整代码:

    #include <stdio.h>
    #include <string.h>
    #define Clean(X,K) memset(X,K,sizeof(X))
    using namespace std ;
    #include <iostream>
    const int Maxn = 2000005 , Base = 26 ;
    int N , Tail = 0 , T[Maxn][Base] , End[Maxn] , Tot = 0 , Len[Maxn];
    unsigned long long HashValue[Maxn] , HashBase = 17 , HashPow[Maxn] = {1} , Ans = 0;
    char S[Maxn * 2] , Tmp[Maxn];
    int Add (int From ) {
    int P = 0 ,R = 1 ;
    unsigned long long int NowHash = 0 , NowLen = 0;
    for (int i = From ; S[i] != '0' ; ++ i) {
        if (!T[P][S[i] - 'a']) T[P][S[i] - 'a'] = ++ Tot;
        P = T[P][S[i] - 'a'] ;
        ++ R;
        NowHash = NowHash * HashBase + S[i] ;
        ++ NowLen ;
    }
    ++ End[P] ;
    Len[P] = NowLen , HashValue[P] = NowHash ;
    return From + R ;
    }
    int NowP ;
    void Ask (int P , int Now , int E ) {
    
    if (Now > E) {
        NowP = P ;
        return ;
    }
    Ask (T[P][S[Now] - 'a'] , Now + 1 , E ) ;
    
    if (End[P]) {
        if (HashValue[NowP] * HashPow[Len[P]] + HashValue[P] == HashValue[P] * HashPow[Len[NowP]] + HashValue[NowP]) {
            Ans += 2 ;
            if (P == NowP) -- Ans ;
        }
    }
    }
    
    int main () {
    //    freopen ("P3449.in" , "r" , stdin) ;
    Clean (T , 0) , Clean (End , 0) , Clean (Len , 0);
    scanf ("%d" , &N) ;
    for (int i = 1 ; i <= N; ++ i) {
        int L ;
        scanf ("%d " , &L) ;
        scanf ("%s" , Tmp) ;
        for (int j = 0 ; j < L; ++ j) S[Tail + j] = Tmp[j] ;
        Tail += L ;
        S[Tail++] = '0' ;
    }
    -- Tail ;
    int Now = 0 , Cnt = -1;
    while (Now <= Tail) Now = Add (Now) ;
    for (int i = 1 ; i < Maxn ; ++ i) HashPow[i] = HashPow[i - 1] * HashBase ;
    int Lst = 0 ;
    Cnt = -1 ;
    for (int i = 1 ; i <= Tail ; ++ i)
        if (S[i] == '0') {
            Ask (0 , Lst , i - 1) ;
            Lst = i + 1 ;
        }
    cout << Ans + N<<endl;
    fclose (stdin) , fclose (stdout) ;
    return 0 ;
    }

评论

  • maoxiangui
    还没有评论
作者: KSkun 更新时间: 2018-02-07 00:59  在Ta的博客查看 举报    1  

感谢远航之曲提供思路,这是他的原博文bzoj 1524 [POI2006]Pal | 远航休息栈

另外本题解同步发布于我的博客[POI2006]PAL-Palindromes 题解 | KSkun's Blog,欢迎来逛~

题解

这个拼接成回文串的情况,肯定是较短串是较长串的前缀时成立,因此可以Trie树处理这些字符串,然后枚举每个字符串的前缀是否也在里面,在的话试着拼接一下。

判断是否是回文串的方法可以用哈希处理。前串的哈希乘上哈希基的后串长次方再加后串的哈希就能完成拼接。对于每一对这样的字符串显然是反着拼也成立,统计答案是要乘2。自己和自己拼算了两次要减掉。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <string>

const int MO = 1e9 + 7, base = 255;

int ch[2000005][26], tot = 1;
int wrd[2000005], cnt[2000005];

int n, len[2000005], hash[2000005], bpow[2000005];
std::string str[2000005];
char strt[2000005];
long long ans = 0;

inline void insert(char* str, int id) {
    int t = 1;
    for(int i = 0; i < len[id]; i++) {
        if(!ch[t][str[i] - 'a']) {
            t = ch[t][str[i] - 'a'] = ++tot;
        } else {
            t = ch[t][str[i] - 'a'];
        }
    }
    wrd[t] = id;
    cnt[t]++;
}

inline int calhash(char* str, int len) {
    long long res = 0;
    for(int i = 0; i < len; i++) {
        res = (res * base + str[i]) % MO;
    }
    return res;
}

int main() {
    scanf("%d", &n);
    bpow[0] = 1;
    for(int i = 1; i < 2000005; i++) {
        bpow[i] = (1ll * bpow[i - 1] * base) % MO;
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d%s", &len[i], strt);
        insert(strt, i);
        hash[i] = calhash(strt, len[i]);
        str[i] = strt;
    }
    for(int i = 1; i <= n; i++) {
        int u = 1;
        for(int j = 0; j < len[i]; j++) {
            u = ch[u][str[i][j] - 'a'];
            if(wrd[u]) {
                if((1ll * hash[wrd[u]] * bpow[len[i]] % MO + hash[i]) % MO == (1ll * hash[i] * bpow[len[wrd[u]]] % MO + hash[wrd[u]]) % MO) {
                    ans = ans + 1ll * cnt[u] * 2;
                }
            }
        }
    }
    printf("%lld", ans - n);
    return 0;
}
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。