Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"计蒜客-T2341\":[\"优秀的拆分\",2,\"[NOI2016]\"],\"洛谷-P3975\":[\"弦论\",5199,\"TJOI2015\"],\"AtCoder-arc151_e\":[\"Keep Being Substring\",122,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/arc151\\\"\\u003eAtCoder Regular Contest 151\\u003c/a\\u003e\"],\"洛谷-P2408\":[\"不同子串个数\",6021,null],\"洛谷-P1659\":[\"拉拉队排练\",5248,\"国家集训队\"],\"Gym-104160H\":[\"P-P-Palindrome\",90,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104160\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)\\u003c/a\\u003e\"],\"Gym-103427M\":[\"String Problem\",289,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103427\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 ICPC Asia Shenyang Regional Contest\\u003c/a\\u003e\"],\"SPOJ-LCS\":[\"Longest Common Substring\",4455,\"\"],\"Gym-103409J\":[\"Suffix Automaton\",176,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103409\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG)\\u003c/a\\u003e\"],\"CodeForces-932G\":[\"Palindrome Partition\",938,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/932\\\"\\u003eICM Technex 2018 and Codeforces Round 463 (Div. 1 + Div. 2, combined)\\u003c/a\\u003e\"],\"洛谷-P4070\":[\"生成魔咒\",4496,\"SDOI2016\"],\"洛谷-P6292\":[\"区间本质不同子串个数\",1075,null],\"洛谷-P5341\":[\"甲苯先生和大中锋的字符串\",1470,\"TJOI2019\"],\"洛谷-P5685\":[\"快乐的 JYY\",702,\"JSOI2013\"],\"洛谷-P4555\":[\"最长双回文串\",6227,\"国家集训队\"],\"洛谷-P6139\":[\"广义后缀自动机(广义 SAM)\",4482,\"模板\"],\"洛谷-P3649\":[\"回文串\",4592,\"APIO2014\"],\"计蒜客-T2351\":[\"品酒大会\",10,\"[NOI2015]\"],\"CodeForces-17E\":[\"Palisection\",1739,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/17\\\"\\u003eCodeforces Beta Round 17\\u003c/a\\u003e\"],\"洛谷-P3804\":[\"后缀自动机(SAM)\",17409,\"模板\"],\"CodeForces-906E\":[\"Reverses\",484,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/906\\\"\\u003eCodeforces Round 454 (Div. 1, based on Technocup 2018 Elimination Round 4)\\u003c/a\\u003e\"],\"洛谷-P3809\":[\"后缀排序\",30433,\"模板\"],\"洛谷-P5496\":[\"回文自动机(PAM)\",5350,\"模板\"],\"HDU-7091\":[\"重叠的子串\",43,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2021CCPC%BB%AA%CE%AA%D4%C6%CC%F4%D5%BD%C8%FC\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2021CCPC华为云挑战赛 \\u003c/a\\u003e \\u003c/div\\u003e\"],\"洛谷-P4762\":[\"Virus synthesis\",1269,\"CERC2014\"],\"洛谷-P5555\":[\"秩序魔咒\",888,null],\"洛谷-P5576\":[\"口头禅\",345,\"CmdOI2019\"],\"洛谷-P1177\":[\"排序\",243547,\"模板\"],\"洛谷-P4287\":[\"双倍回文\",3820,\"SHOI2011\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"George_Plover","updateTime":1700899153000,"title":"字符串高级算法:后缀自动机、后缀数组、回文自动机等","dislikeCnt":0,"content":"\n### 后缀自动机(SAM)\nhttps://oi-wiki.org/string/sam/\n```cpp\nstruct State{//注意状态数最多是字符数的两倍\n int len,link;\n int son[26];\n State(){len\u003dlink\u003d0;memset(son,0,sizeof(son));}\n};\nState st[MAXN];\nint siz,last;\nvoid init_SAM()//root is 0\n{\n siz\u003d0;st[0].len\u003d0;st[0].link\u003d-1;\n siz++;last\u003d0;\n}\nvoid sam_extend(char c)\n{\n int now \u003d siz++;\n st[now].len \u003d st[last].len+1;\n int p\u003dlast;\n while(p!\u003d-1\u0026\u0026!st[p].son[c-\u0027a\u0027]){\n st[p].son[c-\u0027a\u0027]\u003dnow;\n p\u003dst[p].link;\n }\n if(p\u003d\u003d-1)\n st[now].link\u003d0;\n else{\n int q\u003dst[p].son[c-\u0027a\u0027];\n if(st[p].len + 1 \u003d\u003d st[q].len)\n st[now].link \u003d q;\n else{\n int clone\u003dsiz++;\n st[clone]\u003dst[q];\n st[clone].len\u003dst[p].len+1;\n while(p!\u003d-1\u0026\u0026st[p].son[c-\u0027a\u0027]\u003d\u003dq){\n st[p].son[c-\u0027a\u0027]\u003dclone;\n p\u003dst[p].link;\n }\n st[q].link\u003dst[now].link\u003dclone;\n }\n }\n last\u003dnow;\n}\n```\n广义后缀自动机:\n\n(推荐学习的博客:https://www.luogu.com.cn/blog/ChenXingLing/solution-p6139)\n\nendpos集合自然而然变成了字典树上的节点集合。\n\n(修改extend,使其传入last值,并且返回新添节点的号码)\n\n如果允许离线:那么直接在trie树上宽搜拓展即可,拓展的时候起始last取父亲的对应节点。\n\n在线逐串构造:每新开一个串的时候把last置为根(0),然后在extend开头添加特判代码即可:\n```cpp\nif(st[last].son[c-\u0027a\u0027]){\n int q \u003d st[last].son[c-\u0027a\u0027];\n if(st[last].len+1 \u003d\u003d st[q].len)return q;\n int clone\u003dsiz++;st[clone]\u003dst[q];st[clone].len\u003dst[last].len+1;\n while(last!\u003d-1\u0026\u0026st[last].son[c-\u0027a\u0027]\u003d\u003dq){\n st[last].son[c-\u0027a\u0027]\u003dclone;\n last\u003dst[last].link;\n }\n return st[q].link\u003dclone;\n}\n```\n\n\n- 模板题\n\n[problem:洛谷-P3804]\n[problem:洛谷-P6139]\n\n- 基本运用\n[problem:洛谷-P2408]\n[problem:SPOJ-LCS]\n[problem:洛谷-P4070]\n[problem:洛谷-P5341]\n\n- SAM的图的性质\nSAM 的字符转移边构成DAG,图上任何一条从根出发的路径,都表示了原串的一个子串。\n[problem:洛谷-P3975]\n[problem:Gym-103427M]\n\n- 结合其它数据结构\n因为link树的性质,可能和一些数据结构题结合。\n[problem:洛谷-P6292]\n[problem:洛谷-P5576]\n[problem:HDU-7091]\n\n---\n\n### 后缀数组\n\n通常指 $$O(n\\log n)$$ 的后缀排序算法。(存在$O(n)$做法,但实现难度较大)\n\n```cpp\nstruct SA{\n static const int N\u003d1101;\n char s[N];\n int len,sa[N],rk[N],lst_rk[N\u003c\u003c1],lst_sa[N],cnt[N],h[N];\n int ass[N];//rk起点后缀的排名,sa排名对于的后缀起点\n void input(char *str){//输入字符串\n int i;\n for(i\u003d0;str[i];i++)s[i+1]\u003dstr[i];\n s[i+1]\u003d\u0027\\0\u0027;len\u003di;\n }\n bool cmp(int x,int y,int w){//比对,用于重标号\n return lst_rk[x]\u003d\u003dlst_rk[y]\u0026\u0026lst_rk[x+w]\u003d\u003dlst_rk[y+w];\n }\n void get_sa(){\n if(len\u003d\u003d1){//特判长度为1的串\n sa[1]\u003drk[1]\u003d1;return;\n }\n int i,m\u003d300,p,w;\n memset(cnt,0,(m+1)*sizeof(int));\n memset(lst_rk+1,0,2*len*sizeof(int));\n for(i\u003d1;i\u003c\u003dlen;i++)++cnt[rk[i]\u003ds[i]];\n for(i\u003d1;i\u003c\u003dm;i++)cnt[i]+\u003dcnt[i-1];\n for(i\u003dlen;i\u003e\u003d1;i--)sa[ cnt[rk[i]]-- ]\u003di; //最开始做一遍计数排序,初始化sa和rk\n \n for(w\u003d1;w\u003clen;w*\u003d2,m\u003dp)\n {\n for(p\u003d0,i\u003dlen;i\u003elen-w;i--)lst_sa[++p]\u003di;\n for(i\u003d1;i\u003c\u003dlen;i++)\n if(sa[i]\u003ew)lst_sa[++p]\u003dsa[i]-w;//直接利用sa处理好第二关键字排序后的结果\n memset(cnt,0,(m+1)*sizeof(int));\n for(i\u003d1;i\u003c\u003dlen;i++)++cnt[ ass[i] \u003d rk[lst_sa[i]] ];\n for(i\u003d1;i\u003c\u003dm;i++)cnt[i]+\u003dcnt[i-1];\n for(i\u003dlen;i\u003e\u003d1;i--)sa[ cnt[ass[i]]-- ] \u003d lst_sa[i];//基数排序,按第一关键字排序\n memcpy(lst_rk+1,rk+1,len*sizeof(int));\n for(p\u003d0,i\u003d1;i\u003c\u003dlen;i++)\n rk[sa[i]] \u003d cmp(sa[i],sa[i-1],w)?p:++p;//重新标号\n }\n }\n void get_h()\n {\n for(int i\u003d1,k\u003d0;i\u003c\u003dlen;i++)//计算h函数\n {\n if(k)k--;\n while(s[i+k]\u003d\u003ds[ sa[rk[i]-1] + k ])++k;\n h[rk[i]]\u003dk;\n }\n h[1]\u003d0;\n }\n}sa;\n```\n\n- 模板\n[problem:洛谷-P1177]\n[problem:洛谷-P3809]\n\n- 运用(难度较大时可结合数据结构)\n[problem:SPOJ-LCS] 板子\u0026基本运用\n[problem:计蒜客-T2341]\n[problem:计蒜客-T2351] 与并查集结合\n[problem:Gym-103409J] 与线段树离线问题结合\n[problem:AtCoder-arc151_e] 运用\n\n---\n\n### 回文自动机(回文树)\n\n```cpp\nstruct node{\n int len,cnt,ch[26],fail;\n int dep;\n}p[MAXN];\nint siz,n,last;\nchar s[MAXN];\nvoid init(){\n siz\u003d2;\n p[1].fail\u003d2;p[1].len\u003d0;//even root\n p[2].fail\u003d1;p[2].len\u003d-1;//odd root\n last\u003d1;\n}\nvoid extend(char* z,int i){//index from 1\n while(z[i]!\u003dz[i-p[last].len-1])last\u003dp[last].fail;\n if(!p[last].ch[z[i]-\u0027a\u0027]){\n p[last].ch[z[i]-\u0027a\u0027] \u003d ++siz;\n p[siz].len \u003d p[last].len + 2;\n int tmp \u003d p[last].fail;\n while(z[i]!\u003dz[i-p[tmp].len-1])tmp\u003dp[tmp].fail;\n if(p[siz].len\u003e1\u0026\u0026p[tmp].ch[z[i]-\u0027a\u0027]){p[siz].fail\u003dp[tmp].ch[z[i]-\u0027a\u0027];}\n else{p[siz].fail\u003d1;}\n }\n last \u003d p[last].ch[z[i]-\u0027a\u0027];\n p[last].cnt++;\n}\n```\n\n- 模板题\n[problem:洛谷-P5496]\n[problem:洛谷-P4287]\n[problem:洛谷-P4555]\n[problem:洛谷-P3649]\n\n- 简单应用\n[problem:洛谷-P5555]\n[problem:洛谷-P1659]\n[problem:洛谷-P5685]\n\n- 应用\n[problem:CodeForces-17E] 邻接链表PAM\n[problem:洛谷-P4762] dp\n[problem:CodeForces-932G]\n[problem:CodeForces-906E]\n[problem:Gym-104160H] 考察性质\n\n广义回文树\n\n2020 昆明站 F题 Generating Strings(牛客上有)","threadId":176758,"likeCnt":0,"createTime":1700805235000,"isWorkbook":true,"viewCnt":336,"openness":2,"fav":false,"id":4305,"trustable":false}