Codeforces Beta Round #7--D. Palindrome Degree(Manacer)
2024-08-28 21:52:54
题目:http://blog.csdn.net/winddreams/article/details/44218961
求出每一个点为中心的最长字符串,推断该串是不是从开头的回文串。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int p[12000000] , dp[6000000];
char s[12000000] , str[12000000] ;
int init() {
int i , j , l ;
l = strlen(s) ;
str[0] = '&' ;
for(i = 0 , j = 1 ; i < l ; i++) {
str[j++] = '#' ;
str[j++] = s[i] ;
}
str[j++] = '#' ;
str[j] = '\0' ;
return j ;
}
void Manacer(int l) {
int i , max1 = 0 , id ;
p[0] = 0 ;
for(i = 1 ; i < l ; i++) {
if( max1 > i )
p[i] = min(p[2*id-i],max1-i) ;
else
p[i] = 1 ;
while( str[ i-p[i] ] == str[ i+p[i] ] )
p[i]++ ;
if( p[i]+i > max1 ) {
max1 = p[i] + i ;
id = i ;
}
//printf("%d ", p[i]) ;
}
//printf("\n") ;
}
int main() {
int i , j , l , x , ans = 0 ;
scanf("%s", s) ;
l = init() ;
Manacer(l) ;
memset(dp,0,sizeof(dp)) ;
for(i = 2 ; i < l/2+1 ; i++) {
if( i%2 == 1 && i/2 == (p[i]-1)/2 ) {
x = p[i] - 1 ;
dp[x] = dp[x/2] + 1 ;
ans += dp[x] ;
}
else if( i%2 == 0 && p[i] == i ) {
x = p[i] - 1 ;
dp[x] = dp[x/2] + 1 ;
ans += dp[x] ;
}
}
printf("%d\n", ans) ;
}
最新文章
- Oracle Hints详解
- Abstract和Virtual和interface , 派生类中重写 override / new关键字
- dp4
- 第三章:javascript: 列表
- .Net程序员安卓学习之路2:访问网络API
- CentOS配置ssh无密码登录
- Html5中的跨页面消息传输
- [转贴]JAVA 百度地图SDK地图学习——实现定位功能
- 【美妙的Python之二】Python初步
- 使用UDP完成网络通信
- C#调用C++数据类型对照
- 为 Azure IoT Edge 设备部署 Azure Stream Analytics 服务
- BZOJ 2752: [HAOI2012]高速公路(road) [线段树 期望]
- [HNOI2016]矿区
- 痞子衡嵌入式:蓝牙芯片厂商三强(Qualcomm&;CSR, TI, Nordic)产品一览
- 洛谷P4492 [HAOI2018]苹果树(组合数)
- PHP文件管理—实现网盘以及压缩包的功能操作
- Excel中针对IP地址的排序方法
- /etc/hosts和/etc/hostname区别
- slice() 和splice()