HDU 5421 Victor and String(回文树)
2024-09-04 12:16:14
Victor and String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/262144 K (Java/Others)
Total Submission(s): 163 Accepted Submission(s): 78
Problem Description
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.
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.
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这道题目和简单的回文树应用不一样了,它是在两头加字符,不是从左到右只加一边。那么我们怎么解决这样的问题呢?首先s[]数组应该开到长度的两倍,然后以中间作为起始点,分别向两边扩展。然后last应该有两个指针,一个指向左边,一个指向右边另外也应该有两个指针表示两边数组的长度,距离中间的长度在加入新节点的时候,从左边插,和从右边插是一样的,只是有一点在插入一边的时候可能会应该回影响另一边的last指针。具体见代码#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h> using namespace std;
typedef long long int LL;
const int MAX=1e5+5;
char str[MAX];
int n;
struct Tree
{
int next[2*MAX][26];
int fail[2*MAX];
int num[2*MAX];
int len[2*MAX];
int s[2*MAX];
int last[2];
int tot[2];
LL p;
int new_node(int x)
{
memset(next[p],0,sizeof(next[p]));
num[p]=0;
len[p]=x;
return p++;
}
void init()
{
p=0;
new_node(0);
new_node(-1);
last[0]=0;
last[1]=0;
tot[0]=MAX-5;
tot[1]=MAX-6;
fail[0]=1;
}
int get_fail(int x,int k)
{
s[tot[0]-1]=-1;s[tot[1]+1]=-1;
while(s[tot[k]]!=s[tot[k]+(k?-1:1)*(len[x]+1)])
x=fail[x];
return x;
}
int add(int x,int k)
{
x-='a';
s[tot[k]+=(k?1:-1)]=x;
int cur=get_fail(last[k],k);
if(!(last[k]=next[cur][x]))
{
int now=new_node(len[cur]+2);
fail[now]=next[get_fail(fail[cur],k)][x];
next[cur][x]=now;
num[now]=num[fail[now]]+1;
last[k]=now;
if(len[last[k]]==tot[1]-tot[0]+1) last[k^1]=last[k];
}
return num[last[k]];
}
}tree;
int main()
{
int x;char y[10];
while(scanf("%d",&n)!=EOF)
{
tree.init();
LL ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(x==1)
{
scanf("%s",y);
ans+=tree.add(y[0],0);
}
else if(x==2)
{
scanf("%s",y);
ans+=tree.add(y[0],1);
} else if(x==3)
printf("%d\n",tree.p-2);
else
printf("%lld\n",ans);
}
}
return 0;
}
最新文章
- xamarin UWP平台线程交互问题
- css选择器(E[att^=”val”]序号选择器)
- IO(一)
- FreeMarker笔记 第二章 数值和类型
- jquery easyui将form表单元素的值序列化成对象
- EXTJS 4.2 资料 控件之Grid 行编辑绑定下拉框,并点一次触发一次事件
- CSS3几个速记标签2
- Mysql中查看表的类型InnoDB
- 十:Java之泛型
- 指定url和深度的广度优先算法爬虫的python实现
- hdu_5589_Tree(莫队+字典树)
- cms系统架构设计
- ORA-04091错误原因与解决方法
- 通过后缀名和MIME-TYPE检查实现文件类型校验
- mock.js使用总结
- js对字符串的一些操作方法
- springMVC整理05--数据校验、格式化 &; 其他注解 &; 数据绑定流程
- CMakeLists.txt使用
- msf辅助模块的应用——20145301
- java基础-Arrays类常用方法介绍