HDU3068 最长回文 Manacher's Algorithm 马拉车算法 模板
2024-08-29 21:13:56
复习了一下这个算法,
注意数组大小要开两倍大。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000") //c++
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull; typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFFLL; //
const ll nmos = 0x80000000LL; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3fLL; //
const int mod = ; const double PI=acos(-1.0); // #define _DEBUG; //*//
#ifdef _DEBUG
freopen("input", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
/*-----------------------showtime----------------------*/
int p[];
char str[],t[];
int Manacher(char *str,int len){
t[] = '$';t[] = '#';
int tot = ;
for(int i=; i<len; i++){
t[tot++]=str[i];
t[tot++]='#';
} int mx = ,id = ,reslen = ,resCenter = ;
for(int i=; i<tot; i++){
if(i<mx) p[i] = min(p[*id - i] , mx - i);
else p[i] = ;
while(t[i+p[i]] == t[i-p[i]])p[i] ++;
if(p[i]+i > mx){
mx = i + p[i];
id = i;
}
if(reslen < p[i]){reslen = p[i], resCenter = i;} }
return reslen;
}
int main(){ while(~scanf("%s", str)){
int len = strlen(str);
printf("%d\n",Manacher(str,len)-);
}
return ;
}
HDU3068
最新文章
- NET 2.0 OCR文字识别技术(Tesseract 引擎)[转]
- 第五周&;第六周
- linux 下查看文件个数及大小
- 转:一份基础的嵌入式Linux工程师笔试题
- js/jquery获取当前页面URL地址并判断URL字符串中是否包含某个具体值
- [LeetCode]题解(python):121-Best Time to Buy and Sell Stock
- Extjs4.0.7 实现Grid的嵌套
- ORACLE 中极易混淆的几个 NAME 的分析和总结
- NOIP模拟赛---1.生气的LJJ (anger)
- 怎么监控apache运行状态和页面统计
- 实现一个竖直的显示表头的表格(vue版本)
- CSS之BFC及其应用
- AIM Tech Round 4 (Div. 2)ABCD
- vs重装找不到 $(WindowsSdkDir) 配置问题
- Mybatis之旅第一篇-初识Mybatis
- 进入js
- 创建phpinfo(PHP探针)查看自己服务器空间php详细信息
- python textwrap的使用
- 查找xml中的接口名及涉及表名并输出
- 新手小白Linux(Centos6.5)部署java web项目(总)