最长回文子串---Manacher算法
2024-08-26 16:14:46
百度:Manacher算法
代码
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std; int MANACHER(const string &str)
{
string data;
int len = str.length();
data+="$#";
for (int i=;i<len;i++)
{
data+=str[i];
data+='#';
}
data+='@';
//到此预处理完成
len = data.length();
int *temp = new int[len+];
memset(temp,,sizeof(temp));
int MaxIndex=;
int i=,index=,res=; for(;i<len;i++)
{
if (MaxIndex>i)
{
temp[i]=(MaxIndex-i<temp[*index-i]?MaxIndex-i:temp[*index-i]);
}
else
temp[i]=; while (data[i-temp[i]] == data[i+temp[i]])
{
temp[i]++;
}
if(i+temp[i] > MaxIndex)
{
MaxIndex = i+temp[i];
index=i; }
res = (res>temp[i]?res:temp[i]); } delete[]temp;
return res-; } int main()
{
string str ;
int n;
while(cin >> n)
{
while (n--)
{
cin >> str; cout << MANACHER(str)<<endl;
}
} return ;
}
最新文章
- zookeeper源码分析之六session机制
- asp.net MVC excel数据导出
- wpf,离线状态下部分功能不可用。
- js复制内容加版权声明代码
- Linux运维工程师入门须掌握的10个技术点
- cocoa pods
- ios7--系统自带的向右滑动手势返回上一个界面
- leetcode208 happynumber
- ASP.NET MVC企业开发的基本环境
- spring boot到底帮我们做了那些事?
- pwn学习日记Day1 基础知识积累
- ORA-27154: post/wait create failed ORA-27300 ORA-27301 ORA-27302
- Linux基础学习笔记3-用户权限
- 二、JavaScript基础(1)
- oracle addm报告
- db2 v11 安装测试
- 一些input用法
- C++11--Tuple类<;tuple>;
- sublime格式化js、css、html的通用插件-html js css pretty
- Building Projects with Native Code
热门文章
- GCD之全局、主线程
- 【转】开源中国上看到的一个vim的自动配置的好东西,分享下
- go-fasthttp源码分析
- taobao_api项目开坑,自主完成淘宝主要接口的开发-版本:卖家版(非淘宝api)
- 《effective Go》读后记录
- http://codeforces.com/contest/402/problem/E
- An Introduction to Variational Methods (5.1)
- Redis缓存项目应用架构设计二
- JS封装运动框架(另一种写法)
- Js、Jquery定时执行(一次或者重复多次,取消重复)