字符串匹配

一、KMP算法

模式串与主串做匹配时，如果是暴力匹配，在主串某趟匹配失败后，模式串要移动第一位，而主串也有苦难需要回退。

在KMP算法中，如果在匹配过程中，主串不需要回退，当匹配失败后，会从当前位置开始继续匹配。而模式串会滑动到某一位开始比较，而不是没都回退到第一位开始比较。

1、前缀表

• 前缀：除最后一个字符以外，字符串的所有头部子串。

• 后缀：除第一个字符以外，字符串的所有尾部子串。

A星算法

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

一、算法比较

1、Dijkstra算法

Dijkstra算法从物体所在的初始点开始，访问图中的结点。它迭代检查待检查结点集中的结点，并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展，直到到达目标结点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。（我说“最短路径”是因为经常会出现许多差不多短的路径。）在下图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域（注：原文是teal areas）则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）：

DLX舞蹈链

一、精确覆盖问题

精确覆盖问题（英文：Exact Cover Problem）是指给定许多集合 以及一个集合 ，求满足以下条件的无序多元组 ：

例如，若给出

则 为一组合法解。

问题转化

将 中的所有数离散化，可以得到这么一个模型：

给定一个 01 矩阵，你可以选择一些行（row），使得最终每列（column）都恰好有一个 1。 举个例子，我们对上文中的例子进行建模，可以得到这么一个矩阵：

操作系统

一、概念、功能和目标

操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机地工作和资源地分配，以提供给用户和其他软件方便地接口和环境，它是计算机系统中最基本的系统软件。

1、操作系统主要有哪些功能？

从资源管理的角度来看，操作系统有 6 大功能：

1. 进程和线程的管理：进程的创建、撤销、阻塞、唤醒，进程间的通信等。
2. 存储管理：内存的分配和管理、外存（磁盘等）的分配和管理等。
3. 文件管理：文件的读、写、创建及删除等。
4. 设备管理：完成设备（输入输出设备和外部存储设备等）的请求或释放，以及设备启动等功能。
5. 网络管理：操作系统负责管理计算机网络的使用。网络是计算机系统中连接不同计算机的方式，操作系统需要管理计算机网络的配置、连接、通信和安全等，以提供高效可靠的网络服务。
6. 安全管理：用户的身份认证、访问控制、文件加密等，以防止非法用户对系统资源的访问和操作。

数据结构

算法

计算机网络

一、计算机网络的定义

计算机网络是指利用通信线路和设备将分布在不同物理位置的许多自治计算机互连起来，并在网络软件系统的支持下实现资源共享和信息传递的系统。

1、网络分层模型

OSI 七层模型 是国际标准化组织提出的一个网络分层模型，其大体结构以及每一层提供的功能如下图所示：