ACM模版 扩展KMP /* * 扩展KMP * next[i]:x[i...m-1]的最长公共前缀 * extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀 */ void preEKMP(char x[], int m, int next[]) { next[0] = m; int j = 0; while (j + 1 < m && x[j] == x[j + 1]) { j++; } next[1] = j; int k = 1; for (int...

ACM模版 Manacher算法 最长回文子串实例 /* * 求最长回文子串 */ const int MAXN = 110010; char A[MAXN * 2]; int B[MAXN * 2]; void Manacher(char s[], int len) { int l = 0; A[l++] = '$'; //0下标存储为其他字符 A[l++] = '#'; for (int i = 0; i < len; i++) { A[l++] = s[i]; A[l++] = '#'; ...

ACM模版 线索二叉树 typedef char ElemType; // 线索存储标志位 // Link(0)：表示指向左右孩子的指针 // Thread(1)：表示指向前驱后继的线索 typedef enum { Link, Thread } PointerTag; typedef struct BiThrNode { char data; struct BiThrNode *lchild, *rchild; PointerTag ltag; PointerTag rtag; } BiThrNode, *BiThrTree; // 全局变...

ACM模版 字符串匹配 /* * hash(w[0 ... m - 1]) = * (w[0] * 2 ^ (m - 1) + ... + w[m - 1] * 2 ^ 0) % q; * hash(w[j + 1 ... j + m]) = * rehash(y[j], y[j + m], hash(w[j ... j + m - 1]); * rehash(a, b, h) = ((h - a * 2 ^ (m - 1)) * 2 + b) % q; * 可以用q = 2 ^ 32简化%运算 */ #define REHASH(a, b, h) (((h -...

ACM模版 strstr /* * strstr函数 * 功能：在串中查找指定字符串的第一次出现 * 用法：char *strstr(char *strOne, char *strTwo); * 据说strstr函数和KMP的算法效率差不多 */ int main(int argc, const char * argv[]) { char strOne[] = "Borland International"; char strTwo[] = "nation"; char *ptr; ptr = strstr(strO...

最近用Xcode创建新的.cpp文件，结果一下子出现了两个同名不同格式文件，一个.cpp，另一个.hpp，而我原本就需要用到.h格式文件（也可能是.hpp），所以查阅了一些.hpp和.h的资料，毕竟两者看着有些相似，猛一些感觉是近亲关系。 .hpp，本质就是将.cpp的实现代码混入.h头文件当中，定义与实现都包含在同一文件，则该类的调用者只需要include该.hpp文件即可，无需再将cpp加入到project中进行编译。而实现代码将直接编译到调用者的obj文件中，不再生成单独的obj，采用hpp将大幅度减少调用project中的cpp文件数与编译次数，也不用再发布lib与dll文件，因此...

ACM模版 二叉查找树 #include <iostream> template<typename T> //树结点结构 class BSTNode { public: T _key; //结点值 BSTNode *_lchild; BSTNode *_rchild; BSTNode *_parent; //构造函数 BSTNode(T key , BSTNode *lchild, BSTNode *rchild, BSTNode *parent) : _key(key), _l...

ACM模版 赫夫曼编码 main main.cpp #include <iostream> #include "huffman.hpp" int main(int argc, const char * argv[]) { // 源码 char S[] = "I love Golden Dream!"; // char S[] = "I love FishC.com!"; // 压缩码 char s[] = "01101101001111111001011100111111...

大一开学，自己搞了一台27iMac，大一将近结束，进入学院一个名为电脑120的社团，里面有两台闲置的21iMac（全新的，没人用），于是跟组长请示，批走了一台21iMac！ 早在进这个社团前，我就打起了这个21寸iMac的主意，因为我感觉我的不够用，屏幕太小了。 因为知道win可以实现一主机多屏幕的无缝对接，也就是通常说的分屏。于是找了好久关于iMac如何分屏的方法，可是一直未能找到合适的，于是乎便向各路大牛请教，也许是我的想法有些奇葩，几乎没人用一台iMac给另一台iMac分屏，想好多人请教过，终于有人告诉我，需要一根雷电线…… 就知道需要一根雷电线，其他的，什么都不清楚，但是此时电脑...

ACM模版 ACM/ICPC竞赛头文件（C/C++） #include<bits/stdc++.h>包含C++所有头文件。 （PS：不过在国内oj中，poj，hdu等不支持这个函数，这几个oj的编译器问题，其他国外的oj，还有台湾的oj都支持，CF，Topcoder也都支持。） #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstdlib> #include ...

ACM模版 STL简介 关于STL STL（Standard Template Library,标准模版库）是C++语言标准中的重要组成部分。STL以模板类和模版函数的形式为程序员提供了各种数据结构和算法的实现，程序员吐过能够充分的利用STL，可以在代码空间、执行时间和编码效率上获得极大的好处。 STL大致可以分为三大类：算法（algorithm）、容器（container）、迭代器（iterator）。 STL容器是一些模版类，提供了多种组织数据的常用方法，例如：vector（向量，类似于数组）、list（列表，类似于链表）、deque（双向队列）、set（集合）、map（映像）、...

ACM模版 pair STL的<utility>头文件中描述了一个看上去非常简单的模版类pair，用来表示一个二元组或元素对，并提供了按照字典序对元素对进行大小比较运算符模版函数。 Example，想要定义一个对象表示一个平面坐标点，则可以： pair<double, double> p; cin >> p.first >> p.second; pair模版类需要两个参数：首元素的数据类型和尾元素的数据类型。pair模版类对象有两个成员：first和second，分别表示首元素和尾元素。 在<utility>中已经定义了p...

ACM模版 vector 在STL的<vector>头文件中定义了vector（向量容器模版类），vector容器以连续数组的方式存储元素序列，可以将vector看作是以顺序结构实现的线性表。当我们在程序中需要使用动态数组时，vector将会是理想的选择，vector可以在使用过程中动态地增长存储空间。 vector模版类需要两个模版参数，第一个参数是存储元素的数据类型，第二个参数是存储分配器的类型，其中第二个参数是可选的，如果不给出第二个参数，将使用默认的分配器。 下面给出几个常用的定义vector向量对象的方法示例： vector<int> s; ...

ACM模版 邻接表（网） 图描述：结点带权值，边带权值，有向图，属于网结构。 using namespace std; // 边点结构 typedef struct Edge { int tag; int weigh; struct Edge *next; }Edge; // 表结构 typedef struct Table { int data; Edge *first; }Table, *Tables; int main(int argc, const char * argv[]) { int N, M; while (c...