上一篇: 字符串算法复习(三)
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)); } }
字符串告一段落。
Pingback: 字符串算法复习(三) « Hineven!