首页 > 代码库 > ural 1960 Palindromes and Super Abilities
ural 1960 Palindromes and Super Abilities
题意:找出s[1..x]的本质不同的回文串的个数
分析:回文树模板题
/************************************************Author :DarkTongCreated Time :2016年09月21日 星期三 21时17分07秒File Name :a.cpp *************************************************/#include <bits/stdc++.h>using namespace std;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const double eps = 1e-9;const int maxn = 100000 + 10;const int N = 26;struct Palindromic_Tree{ int next[maxn][N]; int fail[maxn]; int cnt[maxn]; int num[maxn]; int len[maxn]; int S[maxn]; int last; int n; int p; int ans[maxn]; int newNode(int l) { for(int i=0;i<N;++i) next[p][i]=0; cnt[p] = 0; num[p] = 0; len[p] = l; return p ++; } void init() { p = 0; newNode(0); newNode(-1); last = 0; n = 0; S[n] = -1; fail[0] = 1; ans[0] = 0; } 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(!next[cur][c]) { int now = newNode(len[cur] + 2); fail[now] = next[get_fail(fail[cur])][c]; next[cur][c] = now; num[now] = num[fail[now]] + 1; ans[n] = ans[n-1] + 1; } else ans[n] = ans[n-1]; last = next[cur][c]; cnt[last] ++; } void count() { for(int i=p-1;i>=0;--i) cnt[fail[i]] += cnt[i]; } void solve(char *s) { int cur = 0; int n = strlen(s+1); for(int i=1; i<=n ; ++i) { cur = next[cur][s[i]-‘a‘]; printf("%d%c", cnt[i], i==n ? ‘\n‘ : ‘ ‘); } }}plt;char s[maxn];int main(){ int T, cas=1; scanf("%s", s+1); plt.init(); for(int i=1; s[i] ; ++ i) plt.add(s[i]); // plt.count(); // plt.solve(s); int n = strlen(s+1); for(int i=1;i<=n;++i) printf("%d%c", plt.ans[i], i==n ? ‘\n‘ : ‘ ‘); return 0;}
ural 1960 Palindromes and Super Abilities
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。