ACM模版 拓扑排序 /* * 拓扑排序 * INIT:edge[][]置为图的邻接矩阵;cnt[0...i...n-1]:顶点i的入度。 */ const int MAXV = 1010; int edge[MAXV][MAXV]; int cnt[MAXV]; void TopoOrder(int n) { int i, top = -1; for (i = 0; i < n; ++i) { if (cnt[i] == 0) { // 下标模拟堆栈 cnt[i] = top; top = i; } } f…

2016年7月18日 0条评论 7点热度 阅读全文

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 i = 2;…

2016年6月19日 0条评论 7点热度 阅读全文

ACM模版 KMP算法 KMP_Pre /* * next[]的含义,x[i - next[i]...i - 1] = x[0...next[i] - 1] * next[i]为满足x[i - z...i - 1] = x[0...z - 1]的最大z值(就是x的自身匹配) */ void KMP_Pre(char x[], int m, int next[]) { int i, j; j = next[0] = -1; i = 0; while (i < m) { while (-1 != j &&…

2016年6月16日 0条评论 7点热度 阅读全文