URAL 2040 Palindromes and Super Abilities 2
2024-08-24 14:30:32
Palindromes and Super Abilities 2
Time Limit: 500MS Memory Limit: 102400KB 64bit IO Format: %I64d & %I64u
Description
Dima adds letters s1, …, sn one by one to the end of a word. After each letter, he asks Misha to tell him how many new palindrome substrings appeared when he added that letter. Two substrings are considered distinct if they are different as strings. Which n numbers will be said by Misha if it is known that he is never wrong?
Input
The input contains a string s1 … sn consisting of letters ‘a’ and ‘b’ (1 ≤ n ≤ 5 000 000).
Output
Print n numbers without spaces: i-th number must be the number of palindrome substrings of the prefix s1 … si minus the number of palindrome substrings of the prefix s1 … si−1. The first number in the output should be one.
Sample Input
abbbba
Sample Output
111111
Notes
We guarantee that jury has C++ solution which fits Time Limit at least two times. We do not guarantee that solution on other languages exists (even Java).
Source
Problem Author: Mikhail Rubinchik (prepared by Kirill Borozdin)
解题:PalindromicTree
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
struct PalindromicTree{
struct node{
int son[],f,len;
void init(int len){
memset(son,,sizeof son);
this->len = len;
}
}e[maxn];
int tot,last,n;
char s[maxn];
int newnode(int len = ){
e[tot].init(len);
return tot++;
}
int getFail(int x){
while(s[n - e[x].len - ] != s[n]) x = e[x].f;
return x;
}
void init(){
last = tot = n = ;
newnode();
newnode(-);
e[].f = ;
s[n] = -;
}
bool extend(int c){
s[++n] = c;
int cur = getFail(last);
bool isExtend = e[cur].son[c] == ;
if(!e[cur].son[c]){
int newson = newnode(e[cur].len + );
e[newson].f = e[getFail(e[cur].f)].son[c];
e[cur].son[c] = newson;
}
last = e[cur].son[c];
return isExtend;
}
}pt;
char str[maxn];
int main(){
while(gets(str)){
pt.init();
for(int i = ; str[i]; ++i){
if(pt.extend(str[i] - 'a')) putchar('');
else putchar('');
}
putchar('\n');
}
return ;
}
最新文章
- Js: Extensible Calendar Examples
- WPF依赖属性详解
- 解决Android时时更新listview数组越界问题
- Java 性能要点:自动装箱/ 拆箱 (Autoboxing / Unboxing)
- Protel对话窗字体显示不完全问题解决办法(PCB)
- drupal中使用drush命令,快速批量的开启和关闭模块
- [M]表格中的天正文字转换问题
- linux 安装 cenos7 和 jdk
- Mybatis-----优化配置文件,基于注解CR
- springcloud之hystrix熔断器-Finchley.SR2版
- __x__(12)0906第三天__<;meta>;标签
- 阿里云ECS Centos7 系统安装图形化桌面
- 墨者学院——密码学加解密实训(Base64转义)
- 「HNOI2016」网络 解题报告
- USB协议枚举过程详解
- (转)Redis集群搭建与简单使用(最少需要 6个节点)
- Hadoop YARN上运行MapReduce程序
- 命令行下的html转pdf工具wkhtmltopdf
- Kafka(一)-- 初体验
- Unity中Surface Shader执行过程