KMP、扩展KMP模板
KMP#include <iostream> #include <string.h> using namespace std; int Next[1110]; void get_Next(char *p){ int m = strlen(p); Next[0] = Next[1] = 0; for (int i=1; i<m; ++i){...
KMP#include <iostream> #include <string.h> using namespace std; int Next[1110]; void get_Next(char *p){ int m = strlen(p); Next[0] = Next[1] = 0; for (int i=1; i<m; ++i){...
最小生成树最小生成树的应用1.最大边权最小的生成树 直接求最小生成树,因为最小生成树的最大边一定是所有生成树里最大边权最小的2.次小生成树 枚举最小生成树上的 n条边,对于其中某条边,从图中删除它以后计算剩余图的最小生成树,一共n-1棵,从这n-1棵生成树中找出最小的一棵,就是整个图的次小生成树。3.边权极差最小生成树 给定一个无向连通图,求出它的所有的生成树中,最大...
dfs模板b站视频链接b站视频链接#include <iostream> #include <algorithm> using namespace std; const int maxn = 20; int arr[maxn]; int vis[maxn]; int stc[maxn]; int n,top; void init(){ for(int i = ...
排序这里有个带图的博客,有助于理解和复习,博客链接冒泡排序(Bubble Sort)思路:一共有n个数,那么需要比n-1趟,每一趟比上次都会少比一个数,因为每次都会把最大的数上浮上去(从小到大排)。时间复杂度: 平均时间复杂度 n2 , 最坏平均时间复杂度 n2 ,最好平均时间复杂度n2(指的是未优化的冒泡排序)。空间复杂度: O(1) , 因为只需要一个temp变量稳定性 :是稳定的,因为...
欧几里得算法用来求最大公约数,又称辗转相除法,时间复杂度可以认为是O(lgn)gcd( a , b ) = gcd( b , a % b )int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a%b); }最小公倍数lcm ( a, b) = a * b / gca( a, b )