126B Password[扩展kmp学习]
2024-09-03 04:46:03
题目大意
给你一个字符串,求它的一个子串使得这个子串即使前缀又是后缀又出现在不是前缀且不是后缀的地方
分析
扩展kmp就是定义z[i]表示i~n的子串与整个串的最长公共前缀的长度是z[i]
所以这个题就是找到一个位置使得z[i]=n-i+1
这样保证了是前缀和后缀
然后再判断之前是否有一个z[j]=z[i]
有的话代表这个长度的串在中间也出现过
直接输出这个即可
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
char s[];
int n,z[],mx;
inline void get_z(){
int i,j,k,l=,r=;
for(i=;i<n;i++){
if(i<=r)z[i]=min(r-i+,z[i-l]);
while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
if(i+z[i]->r)r=i+z[i]-,l=i;
}
}
int main(){
int i,j,k;
scanf("%s",s);
n=strlen(s);
get_z();
for(i=;i<n;i++){
if(z[i]==n-i&&mx>=n-i){
for(j=;j<z[i];j++)cout<<s[j];
puts("");
return ;
}
mx=max(mx,z[i]);
}
puts("Just a legend");
return ;
}
最新文章
- 职责链模式(chain of responsibility Pattern)
- day4----装饰器
- javascript宿主对象之window.location
- Java高效编程之一【创建和销毁对象】
- [转载]SharePoint 网站管理-PowerShell
- idea intellij 快捷键(ubuntu版本)
- Jetty开发指导:Jetty Websocket API
- Citrix 服务器虚拟化之四 Xenserver资源池
- LoadRunner面试题
- 再见:org.apache.catalina.connector.ClientAbortException: java.io.IOException: Connection reset by peer
- Ubuntu里Eclipse关联Jdk
- Hbase思维导图之调优
- SpringMVC(十一) RequestMapping获取Cookie值
- sql server 备份与恢复系列六 文件组备份与还原
- VsCode语言设置为中文
- 线程池之ThreadPoolExecutor
- 【NPM】设置代理
- java web如何获取客户端的请求ip
- absolute之后居中宽度自适应
- convertTo函数
热门文章
- JAVA总结--多线程
- Mybatis-学习笔记(2)Mybatis配置文件
- BZOJ 4919 (树上LIS+启发式合并)
- CopyOnWriteArrayList详解
- Mysql 数据库存储的原理??
- nodejs爬虫编码问题
- [书接上一回]在Oracle Enterprise Linux (v5.7) 中安装DB - (1/4)
- 并发工具CountDownLatch源码分析
- FreeSWITCH Explained / Configuration / Proxy Media
- 02.Linux-CentOS系统Firewalld防火墙配置