字符串算法复习(四)

上一篇: 字符串算法复习(三)

BZOJ 3676

题目大意:给你一个串, 对于这个串的一个回文子串, 称这个串的权值为这个串的长度乘以这个串的出现次数。
问最大的权值是多少。

解题报告

回文树?算了我先不学, 学一发后缀自动机倍增操作…
首先manacher的思路告诉我们本质不同的回文串只有N个…只有能让mxp+p[mxp]变大的回文串才是未出现过的, 否然可以通过mxp对称出现。
然后用后缀自动机倍增查询即可, 后缀自动机拓扑排序(用mxd桶排)后倍增可以快速获得某个子串对应的节点, 具体看代码。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXL = 300030;
namespace SAM {
    const int MAXD = MAXL*2;
    struct Node {
        int ch[26];
        int pre, mxd;
    } d[MAXD];
    int dtot = 1, lst = 1;
    int val[MAXD], pos[MAXD];
    inline void insert (int ch) {
        int u = lst, nu = ++dtot;
        d[lst = nu].mxd = d[u].mxd+1;
        val[nu] = 1, pos[d[nu].mxd] = nu;
        while(u && !d[u].ch[ch]) d[u].ch[ch] = nu, u = d[u].pre;
        if(!u) d[nu].pre = 1;
        else {
            int v = d[u].ch[ch];
            if(d[v].mxd == d[u].mxd+1) d[nu].pre = v;
            else {
                int nv = ++dtot;
                d[nv] = d[v];
                d[nv].mxd = d[u].mxd+1;
                d[v].pre = d[nu].pre = nv;
                while(u && d[u].ch[ch] == v) d[u].ch[ch] = nv, u = d[u].pre;
            }
        }
    }
    int seq[MAXD], buk[MAXD], fa[MAXD][20];
    inline void build () {
        for(int i = 1; i<=dtot; i++) ++ buk[d[i].mxd];
        for(int i = 1; i<=d[lst].mxd; i++) buk[i] += buk[i-1];
        for(int i = 1; i<=dtot; i++) seq[buk[d[i].mxd]--] = i;
        for(int i = dtot; i; i--) val[d[seq[i]].pre] += val[seq[i]], fa[i][0] = d[i].pre;
        for(int lvl = 1; lvl<20; lvl++)
            for(int i = 1; i<=dtot; i++)
                fa[i][lvl] = fa[fa[i][lvl-1]][lvl-1];
    }
    inline int getNode (int l, int r) {
        int u = pos[r];
        for(int i = 19; i>=0; i--)
            if(d[fa[u][i]].mxd >= r-l+1)
                u = fa[u][i];
        return u;
    }
    inline int query (int l, int r) {return val[getNode(l, r)];}
}
char str[MAXL], buf[MAXL*2];
int p[MAXL*2];
int main () {
    scanf("%s", str);
    int len = strlen(str);
    for(int i = 0; i<len; i++) SAM::insert(str[i]-'a');
    SAM :: build();
    for(int i = 0; i<len; i++)
        buf[i<<1] = '#', buf[(i<<1)+1] = str[i];
    buf[len<<1] = '#';
    LL ans = 0;
    int up = len<<1, mxp = 0;
    for(int i = 0; i<=up; i++) {
        if(mxp+p[mxp] >= i) p[i] = min(mxp+p[mxp]-i, p[mxp*2-i]);
        while(i-p[i]>=0 && buf[i-p[i]] == buf[i+p[i]]) ++ p[i];
        -- p[i];
        for(int j = mxp+p[mxp]+1; j<=i+p[i]; j++) {
            int lp = (i-(j-i))>>1, rp = (j-1)>>1;
            int cnt = SAM::query(lp+1, rp+1);
            ans = max(ans, (LL)(rp-lp+1)*cnt);
            //printf("at:[%d, %d]:%d\n", lp, rp, cnt);
        }
        if(i+p[i] > mxp+p[mxp]) mxp = i;
    }
    cout << ans << '\n';
}

解题报告(回文树版本)

PAM好有道理…把PAM搞出来就是个板题了..
几点注意:
1.构造只能沿着fail向上跳, 复杂度有保证(不会证明), 不能像AC自动机那么搞…
2.注意init中0为偶数点, fail指向奇数点…方便构造, 而且rec[0]一定要填一个失配字符…

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXL = 300030;
namespace PAM {
    const int MAXD = MAXL;
    struct Node {
        int ch[26], len, pre, cnt;
    } d[MAXD];
    int lst, len, dtot = 1;
    int rec[MAXL];
    void init () {
        rec[0] = -1;
        d[1].len = -1;
        d[0].pre = 1;
    }
    void insert (int ch) {
        rec[++len] = ch;
        while(rec[len] != rec[len-d[lst].len-1]) lst = d[lst].pre;
        if(!d[lst].ch[ch]) {
            int u = d[lst].ch[ch] = ++dtot;
            d[u].len = d[lst].len+2;
            int t = d[lst].pre;
            while(rec[len] != rec[len-d[t].len-1]) t = d[t].pre;
            if(d[t].ch[ch] != u) d[u].pre = d[t].ch[ch];
        }
        lst = d[lst].ch[ch];
        d[lst].cnt ++;
    }
    int buk[MAXL], seq[MAXL];
    void sumup () {
        for(int i = 2; i<=dtot; i++) ++ buk[d[i].len];
        for(int i = 1; i<=len; i++) buk[i] += buk[i-1];
        for(int i = 2; i<=dtot; i++) seq[buk[d[i].len]--] = i;
        for(int i = dtot-1; i; i--) d[d[seq[i]].pre].cnt += d[seq[i]].cnt;
    }
}
char str[MAXL];
int main () {
    scanf("%s", str);
    int len = strlen(str);
    PAM :: init();
    for(int i = 0; i<len; i++) PAM :: insert(str[i]-'a');
    PAM :: sumup();
    LL ans = 0;
    for(int i = 2; i<=PAM::dtot; i++)
        ans = max(ans, (LL)PAM::d[i].len*PAM::d[i].cnt);
    cout << ans << '\n';
}
//abacaba

BZOJ 3160

题目大意: 自己看…比较复杂

解题报告

首先这个回文匹配的模式和卷积很像。
字符只有两种, 比较套路地用fft处理字符串匹配, 构造多项式P[i]=str[i]-‘a’, 然后多项式平方就可以算出以每个位置为对称轴的失配数量了。
然后组合数学一下再用manacher去除不满足的串…一坨细节…
FFT几乎忘完了, 复习 背 个版又忘记IDFT后要除N…题目还是蛮不错的。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAXL = 100010;
const int MOD  = 1000000007;
const double pi = acos(-1.0);
struct Complex {
    double real, img;
    Complex () {real = img = 0.0;}
    Complex (double a, double b):real(a), img(b) {}
    inline Complex operator + (const Complex & b) const
    {return Complex(real+b.real, img+b.img);}
    inline Complex operator - (const Complex & b) const
    {return Complex(real-b.real, img-b.img);}
    inline Complex operator * (const Complex & b) const
    {return Complex(real*b.real-img*b.img, real*b.img+img*b.real);}
};
inline int bitReverse (int num, int N) {
    int ret = 0, bit = 1;
    while(bit<N) {
        ret <<= 1;
        ret += (bool)(num&bit);
        bit <<= 1;
    }
    return ret;
}
Complex temp[MAXL*3];
void fft (Complex * A, int N, double t) {
    for(int i = 0; i<N; i++) temp[bitReverse(i, N)] = A[i];
    for(int lvl = 2; lvl<=N; lvl<<=1) {
        Complex wn(cos(2.0*pi/(double)lvl), t*sin(2.0*pi/(double)lvl)), t1, t2;
        for(int i = 0; i<N; i+=lvl) {
            Complex w(1.0, 0.0);
            for(int j = 0; j<(lvl>>1); j++, w=w*wn) {
                t1 = temp[i+j], t2 = w*temp[i+(lvl>>1)+j];
                temp[i+j] = t1+t2, temp[i+(lvl>>1)+j] = t1-t2;
            }
        }
    }
    for(int i = 0; i<N; i++) A[i] = temp[i];
}
inline int advPow (int a, int b) {
    int ret = 1;
    while(b) {
        if(b & 1) ret = (LL)ret*a%MOD;
        a = (LL)a*a%MOD;
        b >>= 1;
    }
    return ret;
}
char str[MAXL], buf[MAXL*2];
Complex P[MAXL*3];
int pre[MAXL], suf[MAXL], p[MAXL*2];
int cnts[MAXL*3];
int main () {
    scanf("%s", str);
    int len = strlen(str);
    int lvl = 1;
    while(lvl <= len*2) lvl<<=1;
    for(int i = 0; i<len; i++)
        P[i].real = str[i]-'a', pre[i] = str[i]-'a', suf[i] = str[i]-'a';
    for(int i = 1; i<len; i++) pre[i] += pre[i-1];
    for(int i = len-2; i>=0; i--) suf[i] += suf[i+1];
    fft(P, lvl, 1.0);
    for(int i = 0; i<lvl; i++)
        P[i] = P[i]*P[i];
    fft(P, lvl, -1.0);
    for(int i = 0; i<lvl; i++) cnts[i] = -2*round(P[i].real/(double)lvl);
    for(int i = 0; i<len; i++)
        cnts[i] += pre[i]*2;
    for(int i = len; i<(len<<1)-1; i++) // ?
        cnts[i] += suf[i-len+1]*2;
    for(int i = 0; i<(len<<1)-1; i++) {
        if(i&1) cnts[i] = min(((i>>1)+1)<<1, (len-(i>>1)-1)<<1)-cnts[i];// 夹缝
        else cnts[i] = min(((i>>1)<<1)+1, ((len-(i>>1)-1)<<1)+1)-cnts[i];
    }
    int ans = 0;
    for(int i = 0; i<(len<<1)-1; i++)
        if(i&1) ans = (ans+advPow(2, cnts[i]>>1)-1)%MOD;
        else ans = (ans+advPow(2, (cnts[i]>>1)+1)-1)%MOD;
    for(int i = 0; i<len; i++)
        buf[i<<1] = '#', buf[(i<<1)+1] = str[i];
    int up = len<<1, mxp = 0, sum = 0;
    buf[up] = '#';
    for(int i = 0; i<=up; i++) {
        if(mxp+p[mxp] > i) p[i] = min(mxp+p[mxp]-i, p[mxp*2-i]);
        while(i-p[i] >= 0 && buf[i-p[i]] == buf[i+p[i]]) ++ p[i];
        if(i+(--p[i]) > mxp+p[mxp]) mxp = i;
        if(i&1) sum += (p[i]+1)>>1;
        else sum += p[i]>>1;
        sum %= MOD;
    }
    printf("%d\n", (ans-sum+MOD)%MOD);
}
/*
abaabaa
*/

TSINSEN A1225

题目大意: 自己看…

解题报告

最近学了回文树, 本来准备再练练手, 但是…
算了manacher水过…忘记取模wa*3醉了

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXL = 1000010;
const int MOD  = 19930726;
char str[MAXL];
int p[MAXL];
LL sum[MAXL];
inline int advPow (int a, LL b) {
    int ret = 1;
    while(b) {
        if(b & 1) ret = (LL)ret*a%MOD;
        a = (LL)a*a%MOD;
        b >>= 1;
    }
    return ret;
}
int main () {
    int N; LL K;
    cin >> N >> K;
    scanf("%s", str);
    int mxp = 0;
    for(int i = 0; i<N; i++) {
        if(mxp+p[mxp] >= i) p[i] = min(p[mxp*2-i], mxp+p[mxp]-i);
        while(i-p[i]>=0 && str[i-p[i]] == str[i+p[i]]) ++ p[i];
        -- p[i];
        if(mxp+p[mxp] < i+p[i]) mxp = i;
        ++ sum[p[i]*2+1];
    }
    for(int i = N-1; i>=1; i--) sum[i] += sum[i+2];
    LL ans = 1;
    for(int i = N; i>=1; i--) {
        if(sum[i] >= K) {ans = ans*advPow(i, K)%MOD; K = 0; break;}
        else ans = ans*advPow(i, sum[i])%MOD, K -= sum[i];
    }
    if(K) puts("-1");
    else cout << ans << '\n';
}

CodeForces 17E

给你一个长度 n (1 ≤ n ≤ 2·10^6) 的只由小写字母组成的字符串s。
考虑s的所有连续且回文的子串集合P, 位置不同但内容相同的两个串算作不同。
问从P中选出两个串且他们在s中有公共位置的方法数有几个, 结果对51123987取余。

解题报告

想了好久怎么直接计算…看完cf的tutor发现自己是xx, 转换成总数-有多少对不重合的回文串。
不重复很好算的…可以通过差分处理每个位置开始/结束的回文串数量, 扫一遍就可以了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXL = 2000020;
const int MOD  = 51123987;
char str[MAXL], buf[MAXL*2];
int p[MAXL*2];
pair<int, int> inv[MAXL*2];
LL sumS[MAXL], sumF[MAXL];
int main () {
    int N;
    scanf("%d", &N);
    scanf("%s", str);
    for(int i = 0; i<N; i++)
        buf[i<<1] = '#', buf[(i<<1)+1] = str[i];
    int up = N<<1, mxp = 0;
    buf[up] = '#';
    int itot = 0;
    LL ans = 0;
    for(int i = 0; i<=up; i++) {
        if(mxp+p[mxp] >= i) p[i] = min(p[mxp*2-i], mxp+p[mxp]-i);
        while(i-p[i]>=0 && buf[i-p[i]] == buf[i+p[i]]) p[i]++;
        -- p[i];
        if(i+p[i]> mxp+p[mxp]) mxp = i;
        if(p[i]) inv[++itot] = make_pair(1+((i-p[i])>>1), 1+((i+p[i]-1)>>1));
    }
    for(int i = 1; i<=itot; i++) {
        int l = (inv[i].second-inv[i].first+2)>>1;
        sumS[inv[i].first]++;
        sumS[inv[i].first+l]--;
        if((inv[i].second-inv[i].first+1)&1) sumF[inv[i].first+l-1]++;
        else sumF[inv[i].first+l]++;
        sumF[inv[i].second+1]--;
        ans += (inv[i].second-inv[i].first+2)>>1;
    }
    if((ans-1)&1) ans = ans/2%MOD*((ans-1)%MOD)%MOD;
    else ans = ans%MOD*((ans-1)/2%MOD)%MOD;
    for(int i = 1; i<=N+1; i++) sumS[i] += sumS[i-1];
    for(int i = 1; i<=N+1; i++) sumF[i] += sumF[i-1];
    LL t = 0;
    for(int i = 1; i<=N; i++) {
        (ans -= sumS[i]%MOD*t%MOD) %= MOD;
        (t += sumF[i])%=MOD;
    }
    ans = (ans+MOD)%MOD;
    cout << ans << '\n';
}

UVALive 7041

题目大意: 给两个串A和B, 问有多少四元组(a, b, c, d)满足A[a-b] == B[c-d]并且A[a-b]是回文串。

解题报告

感觉好AC自动机啊, 但是这里多了一个回文串的要求。
对A串建立回文自动机, 然后再自动机上计算标记一通乱搞, 然后把B串喂给自动机就可以 吃 了。
注意别炸int, 开long long。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXL = 200020;
namespace PAM {
    const int MAXD = MAXL;
    struct Node {
        int ch[26];
        int len, pre, cnt;
        LL csuf;
    } d[MAXD];
    int dtot = 1, lst, len;
    int rec[MAXL];
    void init () {
        memset(d, 0, sizeof(d[0])*(dtot+1));
        len = 0; dtot = 1;
        rec[0] = -1;
        d[1].len = -1;
        d[0].pre = 1;
        lst = 1;
    }
    void insert (int ch) {
        rec[++len] = ch;
        while(rec[len] != rec[len-d[lst].len-1]) lst = d[lst].pre;
        if(d[lst].ch[ch] == 0) {
            int u = d[lst].ch[ch] = ++dtot;
            d[u].len = d[lst].len+2;
            int t = d[lst].pre;
            while(rec[len] != rec[len-d[t].len-1]) t = d[t].pre;
            if(u != d[t].ch[ch]) d[u].pre = d[t].ch[ch];
        }
        d[d[lst].ch[ch]].cnt++;
        lst = d[lst].ch[ch];
    }
    int buk[MAXL], seq[MAXD];
    void setup () {
        for(int i = 1; i<=len; i++) buk[i] = 0;
        for(int i = 2; i<=dtot; i++) ++ buk[d[i].len];
        for(int i = 1; i<=len; i++) buk[i] += buk[i-1];
        for(int i = 2; i<=dtot; i++) seq[buk[d[i].len]--] = i;
        for(int i = dtot-1; i; i--) d[d[seq[i]].pre].cnt += d[seq[i]].cnt;
        for(int i = 1; i<dtot; i++) d[seq[i]].csuf = d[seq[i]].cnt+d[d[seq[i]].pre].csuf;
        d[0].cnt = d[0].csuf = 0;
    }
    LL feed (char * str) {
        int u = 1, p = 1;
        LL ans = 0;
        while(str[p] != '\0') {
            while(u != 1 && (str[p] != str[p-d[u].len-1] || !d[u].ch[str[p]-'a'])) u = d[u].pre;
            if(d[u].ch[str[p]-'a']) u = d[u].ch[str[p]-'a'];
            //否然呆在1
            ans += d[u].csuf;
            //printf("at:%d, %c\n", u, str[p]);
            ++ p;
        }
        return ans;
    }
}
char str1[MAXL], str2[MAXL];
int main () {
    int T;
    scanf("%d", &T);
    for(int cas = 1; cas <= T; cas ++) {
        PAM :: init();
        scanf("%s%s", str1, str2+1);
        char * prt = str1;
        while(*prt != '\0') PAM::insert(*prt-'a'), ++prt;
        PAM :: setup();
        printf("Case #%d: %lld\n", cas, PAM::feed(str2));
    }
}

字符串告一段落。