2020-2021:teams:legal_string:lgwza:回文树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:lgwza:回文树 [2020/10/03 23:03] lgwza |
2020-2021:teams:legal_string:lgwza:回文树 [2020/10/03 23:54] (当前版本) lgwza |
||
|---|---|---|---|
| 行 395: | 行 395: | ||
| printf("%d",ans); | printf("%d",ans); | ||
| | | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/7817/A|2020牛客国庆集训派对day1 A]] | ||
| + | |||
| + | **题意**：在给定字符串末尾添加尽可能少的字符使其成为回文串。 | ||
| + | |||
| + | **题解**：该等价于求解以原字符串末尾字符结尾的最长回文子串，直接用回文自动机秒杀。 | ||
| + | |||
| + | **代码**： | ||
| + | |||
| + | <hidden> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int N=4e5+5; | ||
| + | struct Palindromic_Tree{ | ||
| + | int nxt[N][26],fail[N],len[N],S[N],last,n,p; | ||
| + | int newnode(int l){ | ||
| + | memset(nxt[p],0,sizeof(nxt[p])); | ||
| + | len[p]=l; | ||
| + | return p++; | ||
| + | } | ||
| + | void init(){ | ||
| + | p=0; | ||
| + | newnode(0); | ||
| + | newnode(-1); | ||
| + | last=0; | ||
| + | n=0; | ||
| + | S[n]=-1; | ||
| + | fail[0]=1; | ||
| + | } | ||
| + | int get_fail(int x){ | ||
| + | while(S[n-len[x]-1]!=S[n]) x=fail[x]; | ||
| + | return x; | ||
| + | } | ||
| + | void add(int c){ | ||
| + | c-='a'; | ||
| + | S[++n]=c; | ||
| + | int cur=get_fail(last); | ||
| + | if(!nxt[cur][c]){ | ||
| + | int now=newnode(len[cur]+2); | ||
| + | fail[now]=nxt[get_fail(fail[cur])][c]; | ||
| + | nxt[cur][c]=now; | ||
| + | } | ||
| + | last=nxt[cur][c]; | ||
| + | } | ||
| + | }P; | ||
| + | char s[N]; | ||
| + | int main(){ | ||
| + | P.init(); | ||
| + | int n; | ||
| + | scanf("%d",&n); | ||
| + | scanf("%s",s); | ||
| + | for(int i=0;i<n;i++){ | ||
| + | P.add(s[i]); | ||
| + | } | ||
| + | printf("%d",n-P.len[P.last]); | ||
| return 0; | return 0; | ||
| } | } | ||
2020-2021/teams/legal_string/lgwza/回文树.1601737386.txt.gz · 最后更改: 2020/10/03 23:03 由 lgwza
