伊利网站建设评价,wordpress 论坛整合,网站建设企业网站优化,成都抖音代运营正题
题目链接:https://www.luogu.com.cn/problem/P5496 题目大意
长度为nnn的字符串#xff0c;求每个字符串作为结尾有多少个回文串。 解题思路 PAMPAMPAM。
下面是个人对PAMPAMPAM的一些理解(不是讲解)#xff1a;
每个节点表示一个回文串#xff0c;就是根到其的路径…正题
题目链接:https://www.luogu.com.cn/problem/P5496 题目大意
长度为nnn的字符串求每个字符串作为结尾有多少个回文串。 解题思路
PAMPAMPAM。
下面是个人对PAMPAMPAM的一些理解(不是讲解)
每个节点表示一个回文串就是根到其的路径上的字符为一半。为了方便表示长度为奇数的和偶数的这里用了两个根节点。一个奇数根长度为−1-1−1偶数根长度为000。偶数根的failfailfail指向奇数根。failfailfail指针表示该回文串的最长回文后缀(不包括整串)加入新节点时在上个节点的基础上不停的往后跳failfailfail直到该回文串的前一个字符等于当且字符。新节点的failfailfail值同理在新点的父节点的failfailfail上面跳failfailfail。时间复杂度O(n)O(n)O(n)空间复杂度O(nT)O(nT)O(nT) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e610;
int n,len[N],fail[N],num[N],next[N][26],cnt,m,last;
char s[N];
int get_fail(int x){for(;s[n-len[x]-1]!s[n];)xfail[x];return x;
}
int Insert(){int xget_fail(last);if(!next[x][s[n]]){len[cnt]len[x]2;int yget_fail(fail[x]);fail[cnt]next[y][s[n]];num[cnt]num[fail[cnt]]1;next[x][s[n]]cnt;}return (lastnext[x][s[n]]);
}
int main()
{scanf(%s,s1);mstrlen(s1);s[0]26;len[1]-1;fail[0]cnt1;int k0;for(n1;nm;n){s[n](s[n]-ak)%26;printf(%d ,knum[Insert()]);}
}
