首页 > 其他 > 详细

HDU 5421 Victor and String

时间:2015-10-27 16:58:49      阅读:130      评论:0      收藏:0      [点我收藏+]

Victor and String

Time Limit: 1000ms
Memory Limit: 262144KB
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

 
解题:Palindromic Tree
技术分享
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 using LL = long long;
 4 const int maxn = 200010;
 5 struct PalindromicTree {
 6     int son[maxn][26],fail[maxn],num[maxn],s[maxn],len[maxn];
 7     int tot,L,R,last[2];
 8     LL ret;
 9     int newnode(int slen = 0) {
10         num[tot] = 0;
11         memset(son[tot],0,sizeof son[tot]);
12         len[tot] = slen;
13         return tot++;
14     }
15     void init() {
16         ret = tot = last[0] = last[1] = 0;
17         L = maxn>>1;
18         R = L - 1;
19         newnode(0);
20         newnode(-1);
21         fail[0] = fail[1] = 1;
22         memset(s,-1,sizeof s);
23     }
24     int getFail(int kd,int x) {
25         if(kd) while(s[R - len[x] -1] != s[R]) x = fail[x];
26         else while(s[L + len[x] + 1] != s[L]) x = fail[x];
27         return x;
28     }
29     void extend(int kd,int c) {
30         if(kd) s[++R] = c;
31         else s[--L] = c;
32         int cur = getFail(kd,last[kd]);
33         if(!son[cur][c]) {
34             int x = newnode(len[cur] + 2);
35             fail[x] = son[getFail(kd,fail[cur])][c];
36             son[cur][c] = x;
37             num[x] = num[fail[x]] + 1;
38         }
39         last[kd] = son[cur][c];
40         if(len[last[kd]] == R - L + 1) last[kd^1] = last[kd];
41         ret += num[last[kd]];
42     }
43 } pt;
44 int main() {
45     int n,op;
46     char str[10];
47     while(~scanf("%d",&n)) {
48         pt.init();
49         while(n--) {
50             scanf("%d",&op);
51             if(op <= 2) {
52                 scanf("%s",str);
53                 pt.extend(op-1,str[0] - a);
54             } else if(op == 3) printf("%d\n",pt.tot - 2);
55             else if(op == 4) printf("%I64d\n",pt.ret);
56         }
57     }
58     return 0;
59 }
View Code

 

HDU 5421 Victor and String

原文:http://www.cnblogs.com/crackpotisback/p/4914193.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!