SP7586 NUMOFPAL - Number of Palindromes(回文树)
2024-08-30 20:39:52
题意翻译
求一个串中包含几个回文串
题目描述
Each palindrome can be always created from the other palindromes, if a single character is also a palindrome. For example, the string "malayalam" can be created by some ways:
- malayalam = m + ala + y + ala + m
- malayalam = m + a + l + aya + l + a + m
We want to take the value of function NumPal(s) which is the number of different palindromes that can be created using the string S by the above method. If the same palindrome occurs more than once then all of them should be counted separately.
输入输出格式
输入格式:
The string S.
输出格式:
The value of function NumPal(s).
输入输出样例
输入样例#1: 复制
malayalam
输出样例#1: 复制
15
说明
Limitations
0 < |s| <= 1000
题解
这不是一道傻逼模板题吗?
我们只需要好好利用一下cnt数组,统计一下len不为1的回文串。
然后再加上一个|s|的长度就好了。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
int fail,len,ch[26],cnt;
}t[1000010];
char s[1000100];
int n,ans;
void solve()
{
int k=0,tot=1;t[0].fail=t[1].fail=1;t[1].len=-1;s[0]='$';
for(int i=1;i<=n;i++)
{
while(s[i-t[k].len-1]!=s[i])k=t[k].fail;
if(!t[k].ch[s[i]-'a']){
t[++tot].len=t[k].len+2;
int j=t[k].fail;
while(s[i-t[j].len-1]!=s[i])j=t[j].fail;
t[tot].fail=t[j].ch[s[i]-'a'];
t[k].ch[s[i]-'a']=tot;
}
k=t[k].ch[s[i]-'a'];
t[k].cnt++;
}
for(int i=tot;i>=2;i--)
t[t[i].fail].cnt+=t[i].cnt;
for(int i=tot;i>=2;i--)
if(t[i].len!=1)
ans+=t[i].cnt;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
solve();
cout<<ans+n<<endl;
}
最新文章
- 从天猫和支付宝身上学习opcity与rgba
- 面试题目——《CC150》树与图
- 浅谈C语言中结构体的初始化
- Android-BaseLine基础性开发框架
- bpel 之伙伴
- (转)onTouchEvent方法的使用
- IOS 作业项目(4)步步完成 画图 程序(中)
- Server Tomcat v7.0 Server at localhost failed to start.错误可能原因之一
- WEB架构师成长之路-架构师都要懂哪些知识 转
- Gearman + Nodejs + MySQL UDF异步实现 MySQL 到 Redis 的数据同步
- python的hashlib模块
- em,strong,b,i的区别
- [转]shell awk 入门,中级,高级使用
- JVM的内存区域划分以及垃圾回收机制详解
- spring的一些问题
- 关于Excel数据批量导入数据库的案例
- 05_Linux目录文件操作命令2_我的Linux之路
- 构建Java开发环境(JDK)
- jenkins在windows服务器上执行含git push命令的脚本权限不足的解决方法
- Android Handler 机制总结
热门文章
- Pharmaceutical的同学们都看过来,关于补码运算的复习相关内容
- 你不知道的JavaScript(十一)函数参数
- 002.ActiveMQ的安装
- linux 删除命令注意事项(大神勿看)
- [arc067f]yakiniku restaurants
- [Luogu]P3338 [ZJOI2014]力(FFT)
- hdu 5277 YJC counts stars
- YII显示sql进行调试
- hdoj--5256--序列变换(lis变形)
- 8.解决IntelliJ Idea 集成TortoiseSVN 时找不到svn.exe