HDOJ 5421 Victor and String 回文串自己主动机
string and 自己 回文 主动 hdoj
2023-09-11 14:14:10 时间
假设没有操作1,就是裸的回文串自己主动机......
能够从头部插入字符的回文串自己主动机,维护两个last点就好了.....
当整个串都是回文串的时候把两个last统一一下
Victor and String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/262144 K (Java/Others)Total Submission(s): 30 Accepted Submission(s): 9
Problem Description
Victor loves to play with string. He thinks a string is charming as the string is a palindromic string.
Victor wants to playn times.
Each time he will do one of following four operations.
Operation 1 : add a charc to
the beginning of the string.
Operation 2 : add a charc 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
Operation 1 : add a char
Operation 2 : add a char
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 integern means
the number of operations.
The first number of nextn 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
The first number of next
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
/* *********************************************** Author :CKboss Created Time :2015年08月24日 星期一 10时32分04秒 File Name :HDOJ5421.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long int LL; const int maxn=200100; const int C=30; int L,R; int nxt[maxn][C]; int fail[maxn]; LL cnt[maxn]; LL num[maxn]; int len[maxn]; int s[maxn]; int last[2],p,n; LL tot; int newnode(int x) { for(int i=0;i<C;i++) nxt[p][i]=0; num[p]=0; len[p]=x; return p++; } void init() { p=0; newnode(0); newnode(-1); memset(s,-1,sizeof(s)); L=maxn/2; R=maxn/2-1; last[0]=last[1]=0; fail[0]=1; tot=0; } /// d=0 add preffix d=1 add suffix int getfail(int d,int x) { if(d==0) while(s[L+len[x]+1]!=s[L]) x=fail[x]; else if(d==1) while(s[R-len[x]-1]!=s[R]) x=fail[x]; return x; } void add(int d,int c) { c-='a'; if(d==0) s[--L]=c; else s[++R]=c; int cur=getfail(d,last[d]); if(!nxt[cur][c]) { int now=newnode(len[cur]+2); fail[now]=nxt[getfail(d,fail[cur])][c]; nxt[cur][c]=now; num[now]=num[fail[now]]+1; } last[d]=nxt[cur][c]; if(len[last[d]]==R-L+1) last[d^1]=last[d]; tot+=num[last[d]]; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int _; while(scanf("%d",&_)!=EOF) { init(); while(_--) { int kind; char ch[5]; scanf("%d",&kind); if(kind<=2) { kind--; scanf("%s",ch); add(kind,ch[0]); } else if(kind==3) printf("%d\n",p-2); else if(kind==4) printf("%lld\n",tot); } } return 0; }
相关文章
- java基础知识回顾之---java String final类普通方法的应用之字符串数组排序
- 【JAVA】 05-String类和JDK5
- [Typescript] 58. Medium - BEM style string
- [Ramda] Count Words in a String with Ramda's countBy and invert
- [C/C++] String Reverse 字符串 反转
- string之面试题
- [Javascript] String Padding in Javascript using padStart and padEnd functions
- C#中的DataSet、string、DataTable 、对象转换成Json
- [Go] golang 去除 URI 链接中的 query string 参数
- string容器08之string字符串的字串获取
- C#中如何比较2个string类型的日期大小?
- String字符串字符长度校验
- mybatis部分版本异常invalid comparison: java.util.Date and java.lang.String
- JSON parse error: Cannot deserialize instance of `java.lang.String` out of START_ARRAY token
- frida构造string
- JavaScript基础&实战(5)js中的数组、forEach遍历、Date对象、Math、String对象
- 一个 -100.01 的double 在内存中怎么存储的. 一个中文String 在内存中占多少直接 utf-8 / GBK
- 使用tp访问数据库时提示错误: 'PDO' not found, 和not defined constant mysql_attr_init_command 和call an undefined function ThinkTemplatesimpleXml_load_string()函数
- leetcode 606. Construct String from Binary Tree
- C# string转double,double转string