StackPub

正则表达式(Regular Expression,regexp)是一种描述字符串特征的语法规则,用于验证各种字符串是否匹配这个特征,进而实现高级的文本查找,替换,截取内容等操作。 定位符 定位符 说明 ^ 匹配字符串的开始 $ 匹配字符串结尾的位置 选折符当要查找的条件有多个，只要其中一个满足即成立时，使用选择符”|”。 1grep -p --color 'Linux|UNIX' 字符范围 示例 说明 [abc] 匹配字符a,b,c [^abc] 匹配除a,b,c以外的字符 [a-z] 匹配字母a-z范围内的字符 12[^a-z][a-zA-Z0-9] 点字符和限定符点字符”.”用来匹配任意一个字符。 限定符(?,+,*,{})用于匹配某个字符出现的次数。 字符 说明 示例 . 匹配一个任意字符 s.t–>sat,set,sit ? 匹配前面的字符零次或者一次 colou?r–>color,colour + 匹配前面的字符一次或者多次 go+gle–>goole,gooooole...

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 思路： 一维数组array存放皇后位置，array[i]=j 表示i行j列有一个皇后。 判断该位置放置皇后是否合法。 该位置合法，则进行下一行放置。 该位置非法则列值j++，进行第2步的判断。 当放满8个皇后(即i从0–>7)时，找到结果+1。 当某行中的列值(即array[i])>=8时，说明该行在前面行的摆放情况下无解。 则回退到上一行，对上一行的列值j++，进行2步判断。 当row回退到第一行(i=0)，且第一行的列值超出范围(array[0]>=8)时，代表搜索结束。 输出所有可行解。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051...

AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。要搞懂AC自动机，先得有模式树（字典树）Trie、广度优先策略和KMP模式匹配算法的基础知识。 关于AC自动机建立Aho-Corasick automation算法需要三步： 建立模式串的Trie 给Trie添加失配路径 根据AC自动机，搜索待处理的文本 这里以航电OJ上的一道题hdu 2222 KeywordsSearch为例子。 123给定5个单词:say she shr he her一个字符串：yasherhs问一共有多少单词在这个字符串中出现。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210...

位图法(bitmap)位图法就是利用位数组来存储数据状态，其优点就是节省数据存储空间。如下图所示：2 byte的位数组存储数字0,1,5,11。 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 位运算123451 byte (字节)= 8 bit(位);1 KB = 1024 B(字节);1 MB = 1024 KB; 1 GB = 1024 MB; 1 TB = 1024 GB; 与(&) 0&0=0 1&0=0 0&1=0 1&1=1 或(|) 0|0=0 1|0=1 0|1=1 1|1=1 异或(^) 0^0=0 1^0=1 0^1=...

KMP算法是一种改进的字符串匹配算法, 由D.E.Knuth, J.H.Morris和V.R.Pratt提出, 无论是基于确定有限状态自动机机(Determinstic Finite Automata, DFA)的KMP实现还是基于部分匹配表(Parital Match Table, PMT)的KMP实现,其核心思想都是利用匹配失败后的信息,尽可能的减少模式串与主串的匹配次数以达到快速匹配的目的。 朴素模式(Brute-Force)匹配算法朴素的模式匹配算法又称为暴力匹配算法,即当遇到不相等时,回退从头开始逐个比较。 1234567891011121314151617181920212223242526272829303132333435#include<stdio.h>#include<string.h>int find(char *txt, char *pat){ int i = 0; int j = 0; while(i < strlen(txt) && j < strlen(pat)) /* strl...

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.–William Pugh 装在整理至: Skip List（跳跃表）原理详解与实现 skiplist 跳跃表详解及其编程实现 跳表SkipList 跳表是由William Pugh发明的，上面的引言就是他给出的解释。跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳...

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。 1234567891011121314151617181920212223#ifndef TRIE_H#define TRIE_Htypedef struct word_trie_t word_trie_t;typedef enum bool bool;enum bool{ false = 0, true = 1,};struct word_trie_t{ bool (*insert)(word_trie_t *this, char *str); bool (*find_word)(word_trie_t *this, char *str); int (*find_prefix)(word_trie_t *this, char *str); bool (*delete)(word_trie...

图(graph)由顶点(vertex)与边(edge)的构成，研究元素间多对多的关系。 图由顶点(vertex)与边(edge)组成。由一条边链接的两个顶点互为邻接点。若边有方向则此时的图为有向图，连接图的边无方向则为无向图。 若一个无向图中每两个顶点之间都存在一条边，则称这个无向图为完全无向图。完全无向图中若顶点数为n，则边数为n(n-1)/2。 若一个有向图中每两个顶点都存在方向相反的两个边，则称该图为完全有向图。完全有向图中顶点数为n,边数为n(n-1)。 某个顶点的边数称为顶点的度(degree)。有向图中度又分为出度与入度，出度与入度的和为该顶点的度。 图的边数很多接近完全图的称为稠密图，边数很少的称为稀疏图。 与边有关的数据信息称为权(weight)，边上带权值的图称为网图或网络。 路径长度指一条路径上经过的边的数目。 在无向图中，若两顶点之间有路径，则称者两顶点是连通的。若无向图中任意两个顶点之间都连通，则称为连通图。如果不是连通图，则图中极大连通子图称为连通分量。连通图只有一个连通分量，即它本身，非连通图不止一个连通分量。 在有向图中，若任意两个顶点...

平衡二叉树(balance binary tree)是二叉排序树的进化体，由G.M.Adelson-Velsky和E.M. Landis提出的，所以又叫AVL树。 平衡二叉树是指它除了具备二叉排序树的基本特征之外，还具有一个重要的特定：它的左子树与右子树的深度之差(平衡因子)的绝对值不超过1，且都是平衡二叉树。 平衡因子平衡因子(Balance Factor,BF):二叉树结点的左子树深度减去右子树深度的值。平衡二叉树的平衡因子的绝对值不超过1。平衡因子绝对值大于1的结点为根节点的子树就是最小不平衡子树。调整节点之间的链接关的基本方法就是旋转。 旋转左旋(朝左旋转) 左旋规则：在产生的最小不平衡子树根结点右孩子的右孩子处插入结点，即最小不平衡子树的根结点及其右孩子的平衡因子都为负，则以根结点的右孩子为支点进行左旋转，根结点变为支点的左孩子。 12345678910111213static Node* right_right_rotation(AVLTree k1){ AVLTree k2; k2 = k1->right; k1->rig...

二叉排序树(Binary Sort Tree,BST)又称为二叉查找树,二叉搜索树,具有以下性质: 如果左子树不为空,则左子树上所有结点的值都小于根结点的值. 如果右子树不为空,则右子树上所有结点的值均大于根结点的值. 左右子树也分别为二叉排序树. 树中没有相同的结点. 如果用中序遍历二叉排序树,则遍历结果是一个递增序列. 与二分查找类似，查找过程中和关键字比较的次数不超过树的深度。当二叉排序树形态比较对称，此时与折半查找相似，时间复杂度为$O(\log_{2}n)$，最坏情况下二叉排序树是一颗单树(只有左子树或只有右子树)，时间复杂度为$O(n)$。 BST结点结构1234567typedef int Type;typedef struct BSTreeNode{ Type key; /* 关键字(键值) */ struct BSTreeNode *left; /* 左孩子 */ struct BSTreeNode *right; /* 右孩子 */ struct BSTreeNode *parent...