# 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  times. Each time he will do one of following four operations. Operation 1 : add a char  to the beginning of the string. Operation 2 : add a char  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  cases. In each case, the first line has one integer  means the number of operations. The first number of next  line is the integer , meaning the type of operation. If = or , there will be a lowercase English letters followed. .

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

#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;
}
{
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);
}
else if(x==2)
{
scanf("%s",y);
}

else if(x==3)
printf("%d\n",tree.p-2);
else
printf("%lld\n",ans);
}
}
return 0;
}```

0 条评论

## 相关文章

812

### PAT 甲级 1060 Are They Equal

1060. Are They Equal (25) 时间限制 50 ms 内存限制 65536 kB 代码长度限制 16000 B ...

2935

813

3084

3297

### poj------2406 Power Strings

A - Power Strings 难度：☆☆ Time Limit:3000MS     Memory Limit:65536KB     64bit I...

3128

### LeetCode SingleNumber I,II,III

Given a non-empty array of integers, every element appears twice except for one....

1930

### Leetcode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such th...

1839

### HDU 3333 Turing Tree (线段树)

Turing Tree Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768...

3488

3092