题意:
给出一个字符串,问是否存在这样的子串E使得字符串可以表示为EAEBE的形式,其中EAB的长度都为任意值,存在的话输出E的最长长度,否则输出-1
大致思路:
参考http://bbezxcy.iteye.com/blog/1378468 求字符串中存在多少子串使得其既是字符串的前缀也是字符串的后缀。这道题求出所有符合的后缀之后,再判断是否有子串可以成为中间的那个E,并选出长度最小的即可
#include<iostream> #include<cstring> #include<stack> #include<cstdio> #include<map> using namespace std; const int nMax=1000005; char pat[nMax]; int lenp,next[nMax]; void get_next(){ int i,j=-1; next[0]=-1; for(i=1;i<=lenp;i++){ while(j>-1&&pat[j+1]!=pat[i])j=next[j]; if(pat[j+1]==pat[i])j++; next[i]=j; } } map<int,int>mpp; int main(){ int i,j,k,tcs; scanf("%d",&tcs); while(tcs--){ scanf("%s",pat); lenp=strlen(pat); mpp.clear(); get_next(); j=next[lenp-1]; while(j!=-1){ mpp[j]=1; j=next[j]; } int res=-1; for(i=0;i<lenp;i++){ if(mpp[next[i]]!=0){ if(i-next[i]+1>next[i]&&lenp-i-1>=next[i]+1){ res=max(res,next[i]); } } } cout<<res+1<<endl; } return 0; }
相关推荐
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
数据结构中KMP算法过程的Flash演示
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
基于KMP算法的字符串匹配源码, 支持通配符,单匹配和多重匹配。 效率比较高
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
使用并行计算编程工具OpenMp实现kmp串匹配
KMP、Mancher和扩展KMP算法详解,但是其中的参考代码有一点小错误,请自行参考网络
易语言KMP算法模块源码,KMP算法模块,kmp_init,kmp_find,字节集_子字节集寻找
kmp算法:查找一个字符串是不是另一个字符串的子串
KMP 字符串模式匹配详解 KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。而KMP算法的...
kmp算法的原理以及kmp算法的源代码
kmp算法,数据结构的实验报告,大学实验报告,希望能帮到大家