Sicily 1282. Computer Game
2024-10-18 03:08:15
题目地址:1282. Computer Game
思路:
KMP算法,网上有很多资料,参考了一些网上的解题,收获很大,很感谢那些大神们!!!
通过这道题简单说说我对KMP算法的理解吧(大神们勿喷,虽然没人看我的orz~~~~囧)。
首先输入的是要匹配的字符串,如果这个字符串的首字母在整个字符串不重复出现的话,直接一直匹配下去即可。
诶,那重复出现了怎么办,那就从最后一个重复出现的重新开始匹配,那么这就找到优化算法的好方法了,KMP算法的精髓大致是这样的。
这道题具体代码如下:
#include <iostream>
#include <cstdio>
using namespace std; int main() {
int len1, len2;
while (cin >> len1) {
int code[] = {};
int next[] = {};
for (int i = ; i <= len1; i++) {
scanf("%d", &code[i]);
}
int index = ;
for (int i = ; i <= len1; i++) {
index = code[index+] == code[i] ? index+ : ;
next[i] = index;
}
cin >> len2;
index = ;
int test, result;
for (int i = ; i <= len2; i++) {
scanf("%d", &test);
if (index != len1) {
index = code[index+] == test ? index+ : next[index];
if (index == len1) {
result = i-len1;
}
}
}
index == len1 ? cout << result << endl : cout << "no solution\n";
} return ;
}
最新文章
- 如何在windows 10 x64安装佳能 CP900 驱动
- zabbix监控交换机
- Android 手势识别类 ( 三 ) GestureDetector 源码浅析
- 双参数Bellman-ford带队列优化类似于背包问题的递推
- 几个.net的GUI控件库
- Java实现Dijkstra算法求最短路径
- scala 安装
- js+jquery+html实现在三种不通的情况下,点击图片放大的效果
- HTML5 总结-表单-表单元素
- static静态初始化块
- 深圳尚学堂:Web程序员应该会的知识
- 201521123115《Java程序设计》第2周学习总结
- Spring框架学习之依赖注入
- vue-router自动判断左右翻页转场动画
- DNS服务器解析域名的过程
- 【14】-java的单例设计模式详解
- Redis-Cluster操作命令大全
- MYSQL数据库常用操作命令
- PLSql的使用
- version control(关于版本控制)