HDU 4763 (KMP算法)
算法 HDU KMP
2023-09-14 08:58:23 时间
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4763
题目大意:给定一串字符,从中找出符合“EAEBE”格式的E的最大字符数。AB可以是任意数量的任意字符(a-z)。
Sample Input
5
xy
abc
aaa
aaaaba
aaxoaaaaa
Sample Output
0
0
1
1
2
分析:首先枚举判断开始和结尾是否满足作为E,再KMP计算中间是否存在E
代码如下:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define N 1000001 6 int next[N]; 7 char a[N]; 8 9 void getnext(int m){ 10 int i=0,j=-1; 11 next[0]=-1; 12 while(i<=m){ 13 if(j==-1||a[i]==a[j]) 14 { 15 i++; 16 j++; 17 next[i]=j; 18 } 19 else j=next[j]; 20 } 21 } 22 bool kmp(int st,int l){ 23 int j=0; 24 int i=st+1; 25 int ed=l-st-1; 26 while(i<ed) 27 { 28 if(j==-1||a[i]==a[j]){ 29 i++; 30 j++; 31 if(j==st+1) return true; 32 } 33 else j=next[j]; 34 } 35 return false; 36 } 37 bool judge(int ans,int l){ 38 for(int i=0;i<=ans;i++) 39 { 40 if(a[i]!=a[l-ans+i-1]) return false; 41 } 42 return true; 43 } 44 int getsolve(){ 45 int l=strlen(a); 46 int ans=0; 47 getnext(int(l/3)-1); 48 if(l<3) return 0; 49 for(int i=l/3-1;i>=0;i--){ 50 if(judge(i,l)){ 51 if(kmp(i,l)) 52 { 53 ans=i+1; 54 break; 55 } 56 } 57 } 58 return ans; 59 } 60 int main(){ 61 int t; 62 scanf("%d",&t); 63 while(t--){ 64 scanf("%s",a); 65 printf("%d\n",getsolve()); 66 } 67 return 0; 68 }
相关文章
- 前端数据结构与算法系列
- 数据挖掘十大算法
- Java实现 蓝桥杯VIP 算法训练 方格取数
- HDU 4712 Hamming Distance(随机算法)
- 数据结构和算法-面试题
- [YOLOv7/YOLOv5系列算法改进NO.3]添加CoordAtt注意力机制
- ML与Optimality:最优化理论(GD随机梯度下降/QN拟牛顿法/CG共轭梯度法/L-BFGS/TR置信域/GA遗传算法/SA模拟退火算法)在机器学习中的简介、常用方法、案例应用之详细攻略
- ML之xgboost:利用xgboost算法(自带特征重要性可视化+且作为阈值训练模型)训练mushroom蘑菇数据集(22+1,6513+1611)来预测蘑菇是否毒性(二分类预测)
- 基于粒子群优化算法的冷热电联供型综合能源系统运行优化(Matlab代码实现)
- m分集2跳OFDM系统中基于功率分配和子载波配对算法的信道容量matlab仿真
- C/C++程序设计常用算法——贪婪法
- hdoj 2063 过山车 【双边匹配匈牙利算法】
- javascript--枚举算法实现
- HDU 2255 奔小康,赚钱(KM算法模板)
- 数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)