原文英文地址
中文地址
原文：
在长为n的字符串中匹配长度为m的子串，简单匹配算法的时间复杂度为O(m*n)；而KMP算法时间复杂度为O(m+n)。
For the past few days, I’ve been reading various explanations of the Knuth-Morris-Pratt string searching algorithms. For some reason, none of the explanations were
doing it for me. I kept banging my head against a brick wall once I started reading “the prefix of the suffix of the prefix of the…”.
Finally, after reading the same paragraph of CLRS over and o......
阅读全文
大意：最少炸掉多少个公交站就能让士兵无法在指定的K分钟内从源点到达汇点，即在有向图中删除几个点，使得源点到汇点的最短距离大于k。
介绍几个概念:
独立轨：网络中的非汇源点称为内点，而源点和内点的两两无公共点的内点的路径称为独立轨，可以用最小割理论证明。最小割定理有了新解释，那就是在网络中选择一个最小的内点集合并删去，使得源汇之间的所有独立轨都被破坏。
思路：只要想办法把所有长度小于K的独立轨破坏掉即可。这一题实际上求的是有向图的独立轨的数目，即有向图的顶点连通度，只不过有一个额外的要求，即独立......
阅读全文
题目链接~~>
做题感悟：这题很有意思，开始做时根本没想太多，做了一个晚上也没做出来，但是昨天一看晚上突然想到一种方法，灵感来时挡也挡不住啊！
解题思路：这题时间必须同步更新，so~ 应该用bfs 比较好，用bfs 模拟水滴爆裂，怎样模拟呢？ 需要将飞行的水滴放进一个队列，取出时将所有的飞行的水滴都取出同步更新所有点，这里可能要设置两个队列，一个存储以前的水滴，一个存储下一秒的水滴，之后再将下一秒的水滴存入上一秒的队列（这可能不好想，就是设置两个队列，辅队列暂时存下一秒的飞行的水滴，之后还要将其全部转入......
阅读全文
A: 模拟26进制加法即可
/*************************************************************************
> File Name: cf-293-a.cpp
> Author: ALex
> Mail: zchao1995@gmail.com
> Created Time: 2015年02月25日 星期三 13时40分05秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include &l......
阅读全文
getnameinfo:
#include <unistd.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>
int main()
{
struct sockaddr_in addrSrv;
bzero(&addrSrv, sizeof(addrSrv));
addrSrv.sin_family = AF_INET;
addrSrv.sin_addr.s_addr = inet_addr("127.0.0.1");
addrSrv.sin_port = htons(6000);
char hbuf[NI_MAXHOST], sbuf[NI_MAXSERV];
getnameinfo((struct sockaddr*)&addrSrv, sizeof(addrSrv),
hbuf, sizeof(hbuf),
sbuf, sizeof(sbuf),
NI_NUMERICHOST|NI......
阅读全文
今天想试试Linux系统下把java应用程序打包成.jar文件，在网上找了很多相关的博客，发现他们理论讲得很到位，但是按照他们的方式操作发现很多错误，最后综合几篇文章终于尝试成功。多学习别人的失败，更容易带你走向成功，现在把自己操作过程罗列出来（步骤中有部分错误，正是在错误中一步步摸索才获得了最终的成功）。至于理论部分我会在文章末尾贴出来（参考别人文章写的）。如果我理论部分整理的不是很好的话，你可以多参考网上的文章。
实验前准备：FileLength.java 文件一份
实验环境：CentOS6.0 JDK1.6.0_03
实验目的......
阅读全文
原题 http://poj.org/problem?id=2054
题目大意：给你一棵树及每个点的权值和根，你需要把这颗树染色，每个时间只能染一个点（染一个点必须先染他的父亲），所需的花费是当前染色时间*这个点的权值，求最少花费（根必须第一个染），n<=1000 都组数据
这题初看时以为是tree dp ，但没有想出来，还是看了题解，发现是贪心，但是讲的都不明觉厉，只好拿着代码自己想了。。。。
这个题的大体思路就是最大一个要最先选，但是选它必须要选它父亲。于是我们就可以找到一个点X它的V[X]/num[X]是整棵树中最大的（用过的不算，root也不......
阅读全文
/*
只获取本地连接的网卡信息，并不获取无线网卡和虚拟网卡的信息，要想获取无线网卡的信息，需把if(strstr(pAdapter->Description,"PCI")>0 && pAdapter- >Type==MIB_IF_TYPE_ETHERNET)改成if(strstr(pAdapter->Type==71)，若要获取虚拟网卡的信息，需把if(strstr(pAdapter->Description,"PCI")>0 && pAdapter->Type==MIB_IF_TYPE_ETHERNET)改成if(pAdapter->Type==MIB_IF_TYPE_ETHERNET)
*/
#include "stdafx.h"
#include <atlbase.h>
#include <atlconv.h>
#include "iphl......
阅读全文
事务的特性（隔离级别）
A 原子性 说明事务是不可分割的
C 一致性 从数据库的一致状态改变成另一种一致状态
I 隔离性 一个事务不能被其他事务打扰
D 持久性 事务一旦提交就会永久的被保存到数据库
如果不考虑事务的隔离级别，可能会出现以下情况
1、脏读 ： 一个事务读取到了另一个事务为提交的数据。
2、不可重复读：针对同一条记录，前后读取的数据不一样
3、虚读（幻读）：针对一张表，前后读到的记录条数不一样
四种隔离级别：
READ UNCOMMITTED: 1 2 3 都有可能发生
READ COMMITTED: 能避......
阅读全文
修改同事的代码，需要增加传值，可action传值给页面EL表达式${}接收总为空，找了半天没找到为什么，突然发现url地址栏里的路径不是.do，应该同事做了 redirect或url重写；然后找到struts配置文件，发现果真 redirect，下边粘了redirect的注解
redirect="true"时，会调用sendRedirect进行定向，而sendRedirect定向采用的时"再浏 览器发生页面改变
redirect="false"时采用的是server-side forward端的定向;
如果redirect="false" 那在action里处理完操作跳到合适的视图页时候
URL不会改变 而是.do ;
如果在这时候刷新......
阅读全文
ASP.NET对请求处理的过程：当请求一个*.aspx文件的时候，这个请求会被inetinfo.exe进程截获，它判断文件的后缀（aspx）之后，将这个请求转交给 ASPNET_ISAPI.dll，ASPNET_ISAPI.dll会通过http管道（Http PipeLine）将请求发送给ASPNET_WP.exe进程，在ASPNET_WP.exe进程中通过HttpRuntime来处理这个请求，处理完 毕将结果返回客户端。 inetinfo.exe进程：是www服务的进程，IIS服务和ASPNET_ISAPI.DLL都寄存在此进程中。 ASPNET_ISAPI.DLL：是处理.aspx文件的win32组件。其实IIS服务器是只能识别.html文件的，当IIS服务器发现......
阅读全文
tag在互联网应用里尤其多见，首先看下面的关系型数据表：
Book表：
id
name
author
1
The Ruby Programming Language
Mark Pilgrim
2
Ruby on rail
David Flanagan
3
Programming Erlang
Joe Armstrong
Tag表：
tag_name
book_id
ruby
1
ruby
2
web
2
erlang
3
现在用redis将这两张表的数据存起来：
保存Book的数据：
redis 127.0.0.1:6379> incr book_id #用book_id这个key保存book表的id,每次要获得一个新的
......
阅读全文