HDU 5421 Victor and String
Victor and String
This problem will be judged on HDU. Original ID: 5421
64-bit integer IO format: %I64d Java class name: Main
Victor loves to play with string. He thinks a string is charming as the string is a palindromic string.
Victor wants to play n times. Each time he will do one of following four operations.
Operation 1 : add a char c to the beginning of the string.
Operation 2 : add a char c to the end of the string.
Operation 3 : ask the number of different charming substrings.
Operation 4 : ask the number of charming substrings, the same substrings which starts in different location has to be counted.
At the beginning, Victor has an empty string.
Input
The input contains several test cases, at most 5 cases.
In each case, the first line has one integer n means the number of operations.
The first number of next n line is the integer op, meaning the type of operation. If op=1 or 2, there will be a lowercase English letters followed.
1≤n≤100000.
Output
For each query operation(operation 3 or 4), print the correct answer.
Sample Input
6
1 a
1 b
2 a
2 c
3
4
8
1 a
2 a
2 a
1 a
3
1 b
3
4
Sample Output
4
5
4
5
11
Source
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int maxn = ;
struct PalindromicTree {
int son[maxn][],fail[maxn],num[maxn],s[maxn],len[maxn];
int tot,L,R,last[];
LL ret;
int newnode(int slen = ) {
num[tot] = ;
memset(son[tot],,sizeof son[tot]);
len[tot] = slen;
return tot++;
}
void init() {
ret = tot = last[] = last[] = ;
L = maxn>>;
R = L - ;
newnode();
newnode(-);
fail[] = fail[] = ;
memset(s,-,sizeof s);
}
int getFail(int kd,int x) {
if(kd) while(s[R - len[x] -] != s[R]) x = fail[x];
else while(s[L + len[x] + ] != s[L]) x = fail[x];
return x;
}
void extend(int kd,int c) {
if(kd) s[++R] = c;
else s[--L] = c;
int cur = getFail(kd,last[kd]);
if(!son[cur][c]) {
int x = newnode(len[cur] + );
fail[x] = son[getFail(kd,fail[cur])][c];
son[cur][c] = x;
num[x] = num[fail[x]] + ;
}
last[kd] = son[cur][c];
if(len[last[kd]] == R - L + ) last[kd^] = last[kd];
ret += num[last[kd]];
}
} pt;
int main() {
int n,op;
char str[];
while(~scanf("%d",&n)) {
pt.init();
while(n--) {
scanf("%d",&op);
if(op <= ) {
scanf("%s",str);
pt.extend(op-,str[] - 'a');
} else if(op == ) printf("%d\n",pt.tot - );
else if(op == ) printf("%I64d\n",pt.ret);
}
}
return ;
}
最新文章
- eclipse项目打包
- October 27th Week 44th Thursday 2016
- mysql-函数CASE WHEN 语句使用说明
- 示例-创建表格&;使用表格对象
- Cubieboard2裸机开发之(五)看门狗操作
- access的逻辑类型
- iOS基础 - 第三方网络框架
- Android 开发 监听back并且执行home键功能
- 一、selenium 环境搭建
- Xdebug在PHP中的安装配置
- redis : 桌面管理工具 redis-desktop-manager使用指南
- pyhton框架Django之cookie和session
- Python3.x文件处理详解
- [过程记录]Centos7 下 Hadoop分布式集群搭建
- ubuntu(14.04) 网路管理
- [LeetCode] 312. Burst Balloons_hard tag: 区间Dynamic Programming
- 【jQuery源码】preFilter
- Geeks : Kruskal’s Minimum Spanning Tree Algorithm 最小生成树
- 关于phpmailer邮件发送
- atitit.面向过程的编程语言异常处理 c语言 asp vbs 的try catch 实现