kmplayer
- 浏览: 512050 次
- 性别:
- 来自: 北京
-
最新评论
-
jkxydp：
算法运行的结果根本就不对。
BM算法. -
soarwindzhang：
感谢博主的分享，我今天看了您的UFSET非递归的路径压缩时感觉 ...
并查集 -
zhangning290：
楼主好像只考虑了坏字符规则，。没有考虑好后缀
BM算法. -
lsm0622：
文字描述有错误 误导新学者
求有向图的强连通分量(scc):Tarjan算法 -
knightchen：
博主，你太强了！这篇文章对我学习C++多线程很有帮助！谢谢
并发学习之一_windows下ZThread在CodeBlocks上的安装与配置
文章列表
好难,慢慢学.
1,定义:
(1)约定一个字符集Σ和一个字符串 S，设 len(S)=n，且 S[n]='$'，也就是说 S 以一个特殊字符'$'结尾，并且'$'小于Σ中的任何一个字符。除了 S[n]之外，S 中的其他字符都属于Σ。对于约定的字符串 S，从位置 i 开头的后缀直接写成 Suffix(i)。
例如:S=mississippi+'$'
(2)后缀数组
后缀数组SA 是一个一维数组，它保存 1..n 的某个排列
SA[1],SA[2],...SA[n]，并且保证 Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。也就是将S 的 n 个后缀从小 ...
1,后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀树提出的目的是用来支持有效的字符串匹配和查询。
简单点说，后缀树就是将一个给定字符串的所有后缀全部压入一个Trie,然后将只有单个叶子的节点压缩，从而形成的一棵树.
2,后缀树的用途，总结起来大概有如下几种
(1). 查找字符串o是否在字符串S中。
方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。
原理：若o在S中，则o必然是S的某个后缀的前缀。
例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提，采用trie ...
二叉排序树
1,二叉排序树（Binary Sort Tree）又称二叉查找树。
2,它或者是一棵空树；或者是具有下列性质的二叉树：
(1)若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(2)若右子树不空，则右子树上所有结点的值 ...
计算机还没有出现之前，有一种叫做电传打字机（Teletype Model 33）的玩意，每秒钟可以打10个字符。但是它有一个问题，就是打完一行换行的时候，要用去0.2秒，正好可以打两个字符。要是在这0.2秒里面，又有新的字符传过来，那么这个字符将丢失。
于是，研制人员想了个办法解决这个问题，就是在每行后面加两个表示结束的字符。
一个叫做“回车”，告诉打字机把打印头定位在左边界；
另一个叫做“换行”，告诉打字机把纸向下移一行。
这就是“换行”和“回车”的来历.后来，计算机发明了，这两个概念也就被般到了计算机上。那时，存储器很贵，一些科学家认为在每行结尾加两个字符太浪费了，加一个就可以。于是，就出现 ...
先看一段代码:
#include <stdio.h>
int main()
{
char c1=100;
char c2=200;
char c3=c1+c2;
printf("c2==%d\n",c2);
printf("c3==%d\n",c3);
char x=124;
char y=x+x;
printf("x+x== %x\n",x+x);
printf("y==%x\n",y);
}
输 ...
Tire树:
先简单解释一下Trie。“Trie”这个单词来自于"retrieve"，可见它的用途主要是字符串查询。Trie不发tree的音，而发try的音。
应用
题目大意:
统计子串出现的次数,规定子串的长度不超过8.
http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1302
trie算法的思路大概如下：
对输入的长串S 想将所有长度位1-8的子串存入trie树，并在子串末节点上记录下字串出现的次数，然后针对每个输入的查询串s 只要在这颗树上查找 一遍就能找到得到该子串出现的次数。
仍段代码 ...
1,题目大意:
给n条线段,要求划分成尽可能少的子集,使得在同一个子集中的线段两两不重叠.
同时限定线段1和线段2不能在同一子集中.
2,问题分析:
(1)
记每条线段为[Li,Ri], 每个子集的最右端为Bi.
记线段1和2中,L较小的那个为X,另一个为Y.
(2)
如果没有那个限定,容易想到贪心的方法:
将所有线段按L从小到大排序.然后依次处理线段k,如果当前存在某个集合的Bi<=Lk,就将Lk加入此集合中,并更新Bi=Rk.否则新开一个集合放入k.模拟这个过程,最后的集合数就是答案.用堆维护已有集合的信息,时间复杂度是O(nlgn).
(3)
有了限制条件后,原方法不适用了 ...
此文所有的实验都是基于下面的程序：
char str[10];
for (int i = 0; i < 10; i++) str[i] = '!';
执行完后str的值为
str = "!!!!!!!!!!"
我们把str的每个字符都初始化为惊叹号，当str的值发生变化时，使用printf打印str的值，对比先前的 ...
问题:
malloc是开出内存空间。
现在我写了这么一句：
char *name;
name=(char *)malloc(len*sizeof(char));
name指针是个char指针，指向一个char数据，即只保留了一个char数据的长度信息.free的时候它如何知道开出的空间到底有多长?
解答:
(1)malloc是一个库函数，不是由操作系统提供的，绝大部分都是由编译器提供的库包自己实现的。malloc如何实现，依赖于不同的操作系统跟不同的c库。
比如，在linux上面，malloc是调用brk系统调用进行内存分配的,而在windows则是HeapAlloc等等类似的系统函数分配内 ...
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
using namespace std;
class MyAdd : public binary_function<int,int,int>
{
public:
MyAdd(){}
int operator()(int m,int n)
{
return m+n;
}
};
int main()
{
ostream_i ...
1,程序
程序计算机指令的集合,它以文件的形式存储在磁盘上.
2,进程
进程通畅被定义为一个正在运行的程序的实例,是一个程序在其自身的地址空间中的一次执行活动.
进程由两部分组成:
(1)内核对象:操作系统用它来管理进程,也用来存放进程的统计信息.
(2)地址空间:包含所有可执行模块或DLL模块的代码和数据,还包含动态内存分配的空间,如线程堆栈和堆分配空间.
进程是资源申请、调度和独立运行的单位，因此，它使用系统中的运行资源.
进程是不活泼的。进程从来不执行任何东西，它只是线程的容器。若要使进程完成某项操作，它必须拥有一个在它的环境中运行的线程，此线程负责执行包含在进程的地址空间中的代码。 ...
1,算法简介
KMP算法是模式匹配算法的一种改进算法，是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯- 普拉特操作（简称KMP算法）。
2,算法核心
对字串进行预处理.
依靠get_next函数计算出子串中每个字符对应的next[j]的值，从而减少子串回溯的距离，减少时间复杂度。
3,算法性能
简单匹配算法的时间复杂度为O(m*n);可以证明KMP匹配算法的时间复杂度为O(m+n).
4,计算子串的模式函数值.
子串的模式函数值.next[i]有很多版本,这里介绍其中的一种.
定义：
(1)next[0]= -1 意义：任何串的第一个字符的 ...
朴素的字符串匹配算法为什么慢？ 因为它太健忘了，前一次匹配的信息其实可以有部分可以应用到后一次匹配中的，而朴素的字符串匹配算法只是简单的把这个信息扔掉，从头再来，因此，浪费了时间。好好的利用这些信息，自然可以提高运行速度。
1.问题描述
给定目标字符串 T[0..n-1] （基于 0 的数组，数组长度为 n ），和模式串 P[0..m-1] ，问 P 可否匹配 T 中的任意子串，如果可以，返回匹配位置。
2.问题分析
直观分析
brute-force 的蛮力法，适用于较小规模的字符串匹配。
优化
主要介绍 3 种优化办法，分别具体为： Rabin-Karp 算法，有限自动机和 KM ...
(1)#ifndef和 #define组合
一般用于头文件中,防止该头文件被重复引用.
其用法一般为：
#ifndef <标识>
#define <标识>
......... // include or define sth.
#else
......
#endif
<标识>在理论上来说可以是自由命名的，但每个头文件的这个“标识”都应该是唯一的。
标识的命名规则一般是头文件名全大写，前后加下划线，并把文件名中的“.”也变成下划线，如：stdio.h对应的就是:
#ifndef _STDIO_H_
#define _STDIO_H_
...... ...
找出一个带环单链表的环开始的结点
一个n方复杂度的算法:
#include <iostream>
using namespace std;
//定义数据结构
struct Node
{
Node(int i):data(i),next(0){}
int data;
Node* next;
};
//释放带环的节点
void node_circle_free(Node* node,Node* point)
{
static bool flag=false;
if(node->next!=poin ...