题目地址: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 ;
}

最新文章

  1. 如何在windows 10 x64安装佳能 CP900 驱动
  2. zabbix监控交换机
  3. Android 手势识别类 ( 三 ) GestureDetector 源码浅析
  4. 双参数Bellman-ford带队列优化类似于背包问题的递推
  5. 几个.net的GUI控件库
  6. Java实现Dijkstra算法求最短路径
  7. scala 安装
  8. js+jquery+html实现在三种不通的情况下,点击图片放大的效果
  9. HTML5 总结-表单-表单元素
  10. static静态初始化块
  11. 深圳尚学堂:Web程序员应该会的知识
  12. 201521123115《Java程序设计》第2周学习总结
  13. Spring框架学习之依赖注入
  14. vue-router自动判断左右翻页转场动画
  15. DNS服务器解析域名的过程
  16. 【14】-java的单例设计模式详解
  17. Redis-Cluster操作命令大全
  18. MYSQL数据库常用操作命令
  19. PLSql的使用
  20. version control(关于版本控制)

热门文章

  1. F - Count the Colors - zoj 1610(区间覆盖)
  2. Java中直接输出一个类的对象
  3. js打开新的链接2
  4. python_Opencv_使用Matplotlib模块
  5. cmd 命令设置UTF8
  6. Oracle——PL/SQL 语句
  7. javascript 数组 排除null, undefined, 和不存在的元素
  8. Cobar是提供关系型数据库(MySQL)分布式服务的中间件
  9. C#正则怎么判断字符串中是否有汉字
  10. MVC的Model层中的一些便签