言简意赅的讲述KMP算法（附C++实现）
wiki 介绍在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。
思路首先我们可以用常规思路去考虑如果自己实现一个这样的算法应该如何实现
主字符串:S词:W
将两个字符串S和W进行匹配，分别从0，0位置开始匹配
当出现不匹配的情况，重新从1，0位置开始匹配，相当于跳过主字符串的第0位重新匹配一遍。
以此类推
这样的算法很容易可以看出需要O(n2)的时间复杂度，但是也很容易想到
那么KMP算法的时间复杂度是O(n) 是如何做到的呢？
我们再一次回顾刚刚的算法，我们进行优化，其中最需要优化的部分就是第2步：当不匹配的时候S跳过1位再重新匹配，这样会出现前面n位其实已经匹配了但是一旦只移1位会导致全部错位，我们更希望从最相似的地方开始重新匹配。这就是KMP算法。
部分匹配表(PMT)所谓的部分匹配表，实际上表中存放的就是字符串前后缀公共字段最长长度值。
什么是前缀后缀
aba前缀:a， ...
MySQL 表的基本操作
创建语句插入语句修改语句查询语句SELECT [column name] FROM [table name] (WHERE [expression])
column name : 结果表的列名
table name : 选取的表
expression : 约束前面生成的表中的内容.通俗来讲就是根据表达式来显示结果。
连接交叉连接： 实际上就是两者表的笛卡尔积 。 使用CROSS JOIN
内连接内连接查询操作只列出与连接条件匹配的数据行，使用 INNER JOIN 或者直接使用 JOIN 进行连接。
SELECT student.name,score.codeFROM student JOIN score ON score.code=student.code;
外连接左连接、右连接的具体说明可以看下图，其实左连接就是先将两个表的列都拼接起来，接着将左边的表中的行全部输出，右边的表只输出符合条件的行。右连接就相反。
案例1.组合两张表
表1: Person
+-------------+---------+
| 列名 | 类型 |
+---- ...
GDB 调试 从入门到大概会用
简介GDB是GNU开源组织发布的一个强大的UNIX下的程序调试工具。或许，各位比较喜欢那种图形界面方式的，像VC、BCB等IDE的调试，但如果你是在UNIX平台下做软件，你会发现GDB这个调试工具有比VC、BCB的图形化调试器更强大的功能。所谓“寸有所长，尺有所短”就是这个道理。
一般来说，GDB主要帮忙你完成下面四个方面的功能：
1、启动你的程序，可以按照你的自定义的要求随心所欲的运行程序。 2、可让被调试的程序在你所指定的调置的断点处停住。（断点可以是条件表达式） 3、当程序被停住时，可以检查此时你的程序中所发生的事。 4、动态的改变你程序的执行环境。
从上面看来，GDB和一般的调试工具没有什么两样，基本上也是完成这些功能，不过在细节上，你会发现GDB这个调试工具的强大，大家可能比较习惯了图形化的调试工具，但有时候，命令行的调试工具却有着图形化工具所不能完成的功能。让我们一一看来。
命令GDB控制r 开始运行程序直到断点.
contin ...
进程和线程的区别（转）
进程和线程的区别？进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。
简而言之,一个程序至少有一个进程,一个进程至少有一个线程.
线程的划分尺度小于进程，使得多线程程序的并发性高。
另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。
线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进 ...
IPC- 消息队列 详解
Linux下进程间通信方式：管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低 ...
通过LeetCode来了解 回溯算法
回溯算法回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称.
通常回溯算法需要搭配上剪支,否则时间复杂度会很高(因为是遍历每一种题目所要求的可能结果)
BFS广度优先算法实际在二叉树中就是层序遍历,通常是利用一个队列来存储每一层的节点进行遍历,在图中的话需要增加一个存储访问标识的数组.
DFS深度优先算法在二叉树中对应的是前、中、后序遍历,通常是用递归的方法来遍历.在图中的话需要在递归函数的参数中传递一个存储访问标识的数组.
LeetCode - 46 全排列给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], ...
Linux epoll模型详解及源码分析 ( 转)
转载自 CSDN Linux epoll模型详解及源码分析
epoll简介epoll是当前在Linux下开发大规模并发网络程序的热门选择，epoll在Linux2.6内核中正式引入，和select相似，都是IO多路复用（IO multiplexing）技术。
EPOLL 特点支持一个进程打开较大数目的文件描述符（fd）select模型对一个进程所打开的文件描述符是有一定限制的，其由FD_SETSIZE设置，默认为1024/2048。这对于那些需要支持上万连接数目的高并发服务器来说显然太少了，这个时候，可以选择两种方案：一是可以选择修改FD_SETSIZE宏然后重新编译内核，不过这样做也会带来网络效率的下降；二是可以选择多进程的解决方案（传统的Apache方案），不过虽然Linux中创建线程的代价比较小，但仍然是不可忽视的，加上进程间数据同步远不及线程间同步的高效，所以也不是一种完美的方案。
但是，epoll则没有对描述符数目的限制，它所支持的文件描述符上限是整个系统最大可以打开的文件数目，例如，在1GB内存的机器上，这个限制大概为10万左右。
IO效率不会随文件描述符（fd）的增加 ...
深入理解select 模型 （源码分析 ）
本篇主要参照 [深入select多路复用内核源码加驱动实现][1] 和 [Linux内核select源码剖析][2]
select下面这些是用户态下可调用的API函数
# include <sys/select.h>
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);
void FD_CLR(int fd, fd_set *set);
int FD_ISSET(int fd, fd_set *set);
void FD_SET(int fd, fd_set *set);
void FD_ZERO(fd_set *set);
其中以大写的FD_为前缀的函数并非系统调用，而是几个对fd_set进行相关位操作的宏，对应原型定义如下（/usr/include/sys/select.h和/usr/include/bits/select.h）：
typedef long int __fd_mask;
...
Linux I/O模型
什么是I/O复用在客户阻塞（例如标准输入）的时候,服务器进程被杀死.这时候服务器进程虽然正确的给客户端发送了一个FIN，但是客户进程正阻塞在标准输入的过程无法读到这个EOF。这样的进程需要一种预先告知内核的能力，使内核一旦发现进程准备的一个或多个I/O准备就绪就通知进程. 这种能力被称为I/O复用
常见的I/O 模型
阻塞式I/O模型
非阻塞式I/O模型 (轮询访问)
I/O复用
信号驱动式I/O(SIGIO) (例如 SIGIO)
异步I/O
I/O复用select/poll/epoll 三种模型都是I/O复用模型。
信号驱动I/O 模型利用SIGIO 信号实现
异步I/O
区别
Select模型select模型：将所有发生请求的客户端（建议1024以下）进行监听，采用的是轮询模型。int select(int nfds,fd_set readfds,fd_set writefds,fd_set *exceptfds,struct timeval *timeout);
描述：调用此函数监听文件描述符集合中是否有读写请求，如果有，将传入参数进行置位再传出。需要进行轮询 ...
TCP 套接字编程
API介绍include <sys/socket.h>int socket(int family,int type,int protocol)
@family:协议族,为0的时候系统根据后两个参数选择协议. 常用AF_INET@type: 套接字类型,这边区分套接字是TCP还是UDP .如果是TCP就用SOCK_STREAM, 数据报套接字SOCK_DGRAM是UDP使用@protocol: IPPROTO_TCP/IPROTO_UDP/IPROTO_SCTP 分别对应三种传输协议.如果是TCP直接写0也可以返回值: 成功的时候返回非负的套接字.
int connect(int sockfd,const struct sockaddr * servaddr,socklen_t addrlen)
//相应结构体定义
struct sockaddr {
sa_family_t sin_family;//地址族
char sa_data[14]; //14字节，包含套接字中的目标地址和端口信息
};
struct soc ...
Linux 进程间通信-信号
Linux 信号类似于嵌入式中的软中断。由内核发出信号告知进程，且不进行排队。这意味着当多个相同信号同时到来的时候进程将只会执行一次信号处理函数。
几个重要的信号SIGPIPE 管道中止,当写入无人读取的管道时产生该信号,默认终止进程SIGCHLD 子进程结束或者停止时发送SIGALRM 定时器信号,以秒为单位,默认终止进程SIGUSR1/SIGUSR2 自定义信号,默认终止信号SIGINT 键盘输入的退出信号 ctrl+’'SIGOUIT 键盘输入的退出信号 ctrl+cSIGHUP 控制终端的挂起信号 ctrl+z
SIGPIPE网络程序必须要处理SIGPIPE信号,否则当客户端退出的时候服务器仍然向管道中发送数据,会造成crash
SIGCHLD处理僵尸进程
僵尸进程是已经死亡的进程,资源已经释放但是任然占用一个进程号.父进程没有处理SIGCHLD信号或者wait/waitpid()后,子进程结束后没有对子进程进行处理会导致僵尸进程
发送信号
硬件方式: ctrl+c等
软件方式: kill api
安装信号简单方式：signal(int sig,void (*func)( ...
贪心算法
简述每次都是当前最优解.缺点: 也许当前呃最优解并不是最后的最优解.就像人生,也许你现在放弃了一些东西以后就收获更多.
适用场景问题必须能够分解成子问题来解决.**子问题的最优解能够递推到最终问题的最优解.**这种子问题的最优解成为最优子结构.
贪心算法与动态规划不同在于它对每个子问题的解决方案都做出选择,不能回退.
动态规划会保存以前的运算结果,并根据以前的结果对当前进行选择,具备回退功能.
题目分析122 买卖股票只要每天的股票价格比前一天的高,就可以买入前一天的股票第二天马上抛出
class Solution {public: int maxProfit(vector& prices) { //动态规划 // if(prices.size()<=1) // return 0; // int dp[2][2],x=0; // dp[0][0]=0; // dp[0][1]=-prices[0]; // for(int i=1;i<prices.size ...
