比赛 |
20160414 |
评测结果 |
AAAAAAAAAA |
题目名称 |
随机数消除器 |
最终得分 |
100 |
用户昵称 |
ennekings |
运行时间 |
0.841 s |
代码语言 |
C++ |
内存使用 |
130.01 MiB |
提交时间 |
2016-04-14 16:28:39 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define sigma 2
#define maxn 8000005
using namespace std;
typedef long long LL;
char ch[maxn];
LL ans=0;
struct PRT{
int cnt,fa[maxn],prt[maxn][sigma],l[maxn],last;
PRT(){
cnt=1,last=0;
fa[0]=fa[1]=1;
l[0]=0,l[1]=-1;
}
void extend(int c,int n){
int p=last;
while(ch[n-l[p]-1]!=ch[n]) p=fa[p];
if(!prt[p][c]){
int now=++cnt,k=fa[p];
l[now]=l[p]+2;
while(ch[n-l[k]-1]!=ch[n]) k=fa[k];
fa[now]=prt[k][c],prt[p][c]=now;
}
last=prt[p][c];
}
}P;
int main(){
freopen("randomb.in", "r", stdin);
freopen("randomb.out", "w", stdout);
scanf("%s",ch+1);
int n=strlen(ch+1);
for (int i=1; i<=n; i++) {
P.extend(ch[i]-'a', i);
}
cout<<P.cnt-1;
}