URAL 1684. Jack's Last Word KMP
amp 39 word KMP Last URAL
2023-09-11 14:21:02 时间
题目来源:URAL 1684. Jack's Last Word
题意:输入a b 把b分成若干段 每一段都是a的前缀
思路:b为主串 然后用a匹配b 记录到b的i位置最大匹配的长度 然后切割 切割的时候要从后往前
假设a = abac b = abab 那么假设从前往后 首先覆盖了aba 然后b就不能覆盖了 从后往前就能够了 首先覆盖ab 下一次还是ab
由于已经记录了到i位置的最大匹配长度 依据长度从末尾倒退 每次倒退的时候仅仅要是最大的匹配的长度
由于假设在某一次的递推 记录的最大匹配的前缀是x 那么这次应该倒退到i-x
假设不倒退x 倒退小于x的字符y 而且x是能够倒退 剩下的是y-x必然能够倒退 那么一次解决即可了
#include <cstdio> #include <cstring> const int maxn = 100010; char a[maxn], b[maxn]; int f[maxn]; int dp[maxn]; char c[maxn*2]; void get_fail(char* s) { f[0] = f[1] = 0; int n = strlen(s); for(int i = 1; i < n; i++) { int j = f[i]; while(j && s[i] != s[j]) j = f[j]; if(s[i] == s[j]) f[i+1] = j+1; else f[i+1] = 0; } } int main() { while(scanf("%s %s", a, b) != EOF) { get_fail(a); int n = strlen(b), m = strlen(a); int j = 0; for(int i = 0; i < n; i++) { while(j && b[i] != a[j]) j = f[j]; if(a[j] == b[i]) j++; dp[i] = j; if(j == m) j = f[j]; } c[n*2] = 0; int len = n*2, i; for(i = n-1; i >= 0; ) { int k = dp[i]; if(k == 0) break; for(int j = i; j > i-k; j--) c[--len] = a[j-i+k-1]; c[--len] = ' '; i = i-k; } if(i != -1) puts("Yes"); else { puts("No"); puts(c+len+1); } } return 0; }
相关文章
- 用SpriteBuilder简化"耕牛遍地走"的动画效果(三)
- [android] No resource found that matches the given name 'Theme.AppCompat.Light'
- 【Linux&Unix】使用nohup让程序永远后台运行
- Java 基础:认识&理解关键字 native 实战篇
- [AWS DA - Cloud Fundamentals] 2.5 Networking & Elasticity
- [PWA] 9. Service worker registerion && service work's props, methods and listeners
- [Bootstrap] 8. 'Collapse', data-target, data-toggle & data-parent
- [Typescript] Get full type safe for discriminatedUnion type with 'type' & 'subtype' (2 levels)
- [Javascript] Regex: '$`', '$&', '$''
- 用户 'sa' 登录失败。原因: 该帐户被禁用。 (Microsoft SQL Server,错误: 18470)
- WCF 在应用程序级别之外使用注册为 allowDefinition='MachineToApplication' 的节是错误的。
- 错误1Files 的值“<<<<<<< .mine”无效。路径中具有非法字符。
- VB.net:VB.net编程语言学习之添加引用&打包安装项目的简介、案例应用之详细攻略
- DataScience&ML:风控场景之模型监控的意义、具体内容【线上线下一致性监控、前端监控(客群稳定性/风控决策全流程)、后端监控(模型性能评估/资产质量分析)、模型表现监控和模型影响】之详细攻略
- 智能优化算法——模拟退火法(Python&Matla实现)
- httpd: Could not reliably determine the server's fully qualified domain name
- HDU 2732 Leapin' Lizards(拆点+最大流)
- 【编程实践】Raft 算法的原理 & go代码实例
- Could not find class '****', referenced from method #####
- 解决ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/tmp/mysql.sock' (2)
- UVA 1484 - Alice and Bob's Trip(树形DP)
- MySQL下载安装 & 完美卸载
- 每日一小练1——完全平方数问题(Python&C语言实现)