东拼西凑的模板·持续更新中
2018-06-17 20:41:34来源：未知 阅读 ()
一.常用算法
文中代码大量来自ACM算法模板 · 一些常用的算法模板-模板合集（稍加修改）
1.1 快速幂
1 ll qpow(ll x, ll n , ll mod) 2 { 3 ll ans=1; 4 while(n){ 5 if(n&1){ 6 ans=(ans*x)%mod; 7 n--; 8 } 9 x=(x*x)%mod; 10 n>>=1; 11 } 12 return ans; 13 }
1.2 gcd
1 ll gcd(ll a,ll b){ 2 return b==0?a:gcd(b,a%b); 3 }
1.3 大数乘法
1 long long quick_multiply(long long a, long long b, long long mod) { 2 long long result = 0; 3 while (b) { 4 result = (result + (b % 2 * a) % mod) % mod; 5 a = a * 2 % mod; 6 b = b / 2; 7 } 8 }
1 for(i=0; i<LA-1; i++) 2 for(j=0; j<LB-1; j++) 3 c[i+j]+=a[i]*b[j]; 4 5 for(i=0; i<LA+LB; i++) 6 if(c[i]>=10) 7 { 8 c[i+1]+=c[i]/10; 9 c[i]%=10; 10 }
1 //https://www.cnblogs.com/king-ding/p/bigIntegerMul.html 2 #include<stdio.h> 3 #include<string.h> 4 #include<malloc.h> 5 6 #define and && /**************/ 7 #define or || /* python风格 */ 8 #define not ! /* */ 9 #define Int(X) (X - '0') /**************/ 10 11 int *multiBigInteger(const char *, const char *); 12 int checkNum(const char *); 13 14 int main(void) 15 { 16 char num1[100] = {'\0'}, num2[100] = {'\0'}; 17 printf("Please input two nunber(less than 100 digits):\n> "); 18 while(scanf("%s%s", num1, num2) != EOF) 19 { 20 int *result = NULL; 21 int i, change = 0; 22 //对输入的数据进行检验 23 if(strlen(num1) > 100 or strlen(num2) > 100) 24 { 25 printf("per number must less than 100 digits\n"); 26 return 1; 27 } 28 29 if(checkNum(num1) or checkNum(num2)) 30 { 31 printf("ERROR: input must be an Integer\n"); 32 return 1; 33 } 34 35 printf("num1:\t%s\nnum2:\t%s\n", num1, num2); 36 37 result = multiBigInteger(num1, num2); 38 39 /* 输出结果result，result[0]保存着result的长度， 40 * 所以下标要从1开始 */ 41 printf("result:\t"); 42 for(i = 1; i <= result[0]; i++) 43 { 44 if(result[i] != 0) //这一步用来去掉前导0,第一位为0跳过不输出 45 change = 1; 46 if(not change) 47 { 48 if(i > 1) //这一步用来判断结果是否为0, 49 { //如果结果第二位还是0,就判断为0 50 printf("0"); 51 break; 52 } 53 continue; 54 } 55 printf("%d", result[i]); 56 } 57 printf("\n"); 58 printf("\nPlease input two nunber(less than 100 digits):\n> "); 59 } 60 return 0; 61 } 62 63 //用于检测输入的是否是数字，如果是就返回0,不是就返回1 64 int checkNum(const char *num) 65 { 66 int i; 67 for(i = 0; (size_t)i < strlen(num); i++) 68 { 69 if(num[i] < '0' or num[i] > '9') 70 { 71 return 1; 72 } 73 } 74 return 0; 75 } 76 77 //返回结果result，为一片内存块，类似数组 78 int *multiBigInteger(const char *num1, const char *num2) 79 { 80 int *result = NULL; //用来保存最终结果 81 int num1Len = strlen(num1); //num1的长度 82 int num2Len = strlen(num2); //num2的长度 83 int resultLen; //结果的最大长度 84 int i, j; //循环计数器 85 resultLen = num1Len + num2Len; //结果长度最大为num1长度和num2长度之和 86 //初始化result为0 87 result = (int *)malloc((resultLen+1)*sizeof(int)); 88 memset(result, 0, (resultLen+1)*sizeof(int)); 89 90 result[0] = resultLen; //result的第一位是用来保存result的长度的。 91 /* num1乘以num2,由于这里采用先不进位的算法，所以算法是按从左到右 92 * 按顺序来乘，然后将每位的结果保存到result的每一位中，循环一次 93 * reult就从下一位开始求和。如下：(左边为正常算法，右边为本程序算法) 94 * 95 * 54321 | 54321 96 * × 123 | × 123 97 * ------- | -------- 98 * 162963 | 54321 99 * 108642 | 108642 100 * 54321 | 162963 101 * -------- | --------- 102 * 6681483 | 6681483 103 * 104 * */ 105 for(j = 0; j < num2Len; j++) 106 { 107 for(i = 0; i < num1Len; i++) 108 { 109 /* result第一位是用来保存result长度的，而第二位是保存结果最后的进位的 110 * 没有进位，则result[1]为0，所以每位相乘之和是从第三位（即result[2]） 111 * 开始。这里是本程序的比较巧妙的地方，需要仔细想想。 112 * */ 113 result[i+j+2] += Int(num1[i]) * Int(num2[j]); 114 } 115 } 116 117 /* 这个循环用来处理进位的，所以要从result的最后一位一直处理到首位。 118 * 要注意result的总长度是resultLen+1,有一位是保存result的长度，而 119 * C语言下标是从0开始，所以result的最后一位的下标就是resultLen，而 120 * 第一位就是1。*/ 121 for(i = resultLen; i > 1; i--) 122 { 123 result[i-1] += result[i]/10; 124 result[i] = result[i]%10; 125 } 126 printf("num1Len:%d\nnum2Len:%d\n", num1Len, num2Len); 127 return result; 128 } 129 130 大整数相乘2完整代码
1 //JAVA 大数相乘 2 import java.math.BigInteger; 3 import java.util.*; 4 import java.io.*; 5 6 public class Main 7 { 8 public static void main(String args[]) 9 { 10 Scanner cin = new Scanner(System.in); 11 BigInteger a = cin.nextBigInteger(); 12 BigInteger b = cin.nextBigInteger(); 13 BigInteger ans = a.multiply(b); 14 System.out.println(ans); 15 } 16 }
1.4高精度幂运算
1 //JAVA 高精度幂 2 import java.io.*; 3 import java.math.BigDecimal; 4 import java.util.*; 5 6 public class Main 7 { 8 public static void main(String args[]) 9 { 10 Scanner cin = new Scanner(System.in); 11 while(cin.hasNext()) 12 { 13 BigDecimal ans = cin.nextBigDecimal(); 14 int n = cin.nextInt(); 15 String res = ans.pow(n).stripTrailingZeros().toPlainString(); //整数去掉后面的0和小数点 16 if(res.startsWith("0")) //去掉前导0 17 { 18 res = res.substring(1); 19 } 20 System.out.println(res); 21 } 22 } 23 }
更多java大数使用见：https://blog.csdn.net/morejarphone/article/details/51884888
1.5 KMP
1 https://blog.csdn.net/y990041769/article/details/38379317 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include <iostream> 6 #include <string> 7 using namespace std; 8 int f[15000]; 9 void getfill(string s) 10 { 11 memset(f,0,sizeof(f)); //根据其前一个字母得到 12 for(int i=1;i<s.size();i++) 13 { 14 int j=f[i]; 15 while(j && s[i]!=s[j]) 16 j=f[j]; 17 f[i+1]=(s[i]==s[j])?j+1:0; 18 } 19 } 20 int find(string a,string s) 21 { 22 int ans=0; 23 getfill(s);int j=0; 24 for(int i=0;i<a.size();i++) 25 { 26 while(j && a[i]!=s[j]) 27 j=f[j]; 28 if(a[i]==s[j]) 29 j++; 30 if(j==s.size()){ 31 ans++; 32 } 33 } 34 return ans; 35 } 36 int main() 37 { 38 string s,a; 39 int T; 40 scanf("%d",&T); 41 while(T--) 42 { 43 getchar(); 44 cin>>s>>a; 45 int ans=find(a,s); 46 printf("%d\n",ans); 47 } 48 return 0; 49 }
1.6 二分查找
1 int l=0,r=n; 2 while(l+1<r){ 3 int k=l+r>>1; 4 if(check(k))l=k; 5 else r=k; 6 }
1.7 矩阵快速幂
1 //https://blog.csdn.net/wust_zzwh/article/details/52058209 2 const int N=10; 3 int tmp[N][N]; 4 void multi(int a[][N],int b[][N],int n) 5 { 6 memset(tmp,0,sizeof tmp); 7 for(int i=0;i<n;i++) 8 for(int j=0;j<n;j++) 9 for(int k=0;k<n;k++) 10 tmp[i][j]+=a[i][k]*b[k][j]; 11 for(int i=0;i<n;i++) 12 for(int j=0;j<n;j++) 13 a[i][j]=tmp[i][j]; 14 } 15 int res[N][N]; 16 void Pow(int a[][N],int n) 17 { 18 memset(res,0,sizeof res);//n是幂，N是矩阵大小 19 for(int i=0;i<N;i++) res[i][i]=1; 20 while(n) 21 { 22 if(n&1) 23 multi(res,a,N);//res=res*a;复制直接在multi里面实现了； 24 multi(a,a,N);//a=a*a 25 n>>=1; 26 } 27 }
二.素数
2.1 素数筛
1 const int MAX = 100; 2 //快速素数筛，只筛选小于等于素数i的素数与i的乘积，既不会造成重复筛选，又不会遗漏。时间复杂度几乎是线性的。 3 //模板来源https://blog.csdn.net/stack_queue/article/details/53560887 4 long long su[MAX],cnt; 5 bool isprime[MAX]; 6 void prime() 7 { 8 cnt=1; 9 memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数 10 isprime[0]=isprime[1]=0;//0和1不是素数 11 for(long long i=2;i<=MAX;i++) 12 { 13 if(isprime[i]) 14 su[cnt++]=i;//保存素数i 15 for(long long j=1;j<cnt&&su[j]*i<MAX;j++) 16 { 17 isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数 18 } 19 } 20 } 21 int main() 22 { 23 prime(); 24 for(long long i=1;i<cnt;i++) 25 printf("%d ",su[i]); 26 return 0; 27 }
2.2 米勒罗宾素数测试
1 //https://blog.csdn.net/u013654696/article/details/40056179 2 // 18位素数：154590409516822759 3 // 19位素数：2305843009213693951 (梅森素数) 4 // 19位素数：4384957924686954497 5 LL prime[6] = {2, 3, 5, 233, 331}; 6 LL qmul(LL x, LL y, LL mod) { // 乘法防止溢出， 如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法 7 8 9 return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod; 10 /* 11 LL ret = 0; 12 while(y) { 13 if(y & 1) 14 ret = (ret + x) % mod; 15 x = x * 2 % mod; 16 y >>= 1; 17 } 18 return ret; 19 */ 20 } 21 LL qpow(LL a, LL n, LL mod) { 22 LL ret = 1; 23 while(n) { 24 if(n & 1) ret = qmul(ret, a, mod); 25 a = qmul(a, a, mod); 26 n >>= 1; 27 } 28 return ret; 29 } 30 bool Miller_Rabin(LL p) { 31 if(p < 2) return 0; 32 if(p != 2 && p % 2 == 0) return 0; 33 LL s = p - 1; 34 while(! (s & 1)) s >>= 1; 35 for(int i = 0; i < 5; ++i) { 36 if(p == prime[i]) return 1; 37 LL t = s, m = qpow(prime[i], s, p); 38 while(t != p - 1 && m != 1 && m != p - 1) { 39 m = qmul(m, m, p); 40 t <<= 1; 41 } 42 if(m != p - 1 && !(t & 1)) return 0; 43 } 44 return 1; 45 }
三.数学相关
3.1 扩展欧几里得算法
1 int exgcd(int a,int b,int &x,int &y) 2 { 3 if(b==0) 4 { 5 x=1; 6 y=0; 7 return a; 8 } 9 int r=exgcd(b,a%b,x,y); 10 int t=x; 11 x=y; 12 y=t-a/b*y; 13 return r; 14 }
3.2 向量基本计算方法
1 #include<cstdio> 2 #include<cstring> 3 #include<cctype> 4 #include<cmath> 5 #include<algorithm> 6 #define eps 1e-8 7 using namespace std; 8 9 struct Point 10 { 11 double x,y; 12 Point(){} 13 Point(double x,double y):x(x),y(y){} 14 double operator *(const Point B)const{ return x*B.y-y*B.x; } 15 Point operator -(const Point B)const{ return Point(x-B.x,y-B.y); } 16 Point operator +(const Point B)const{ return Point(x+B.x,y+B.y); } 17 Point operator *(const double B)const{ return Point(x*B,y*B); } 18 }A,B,C,D,L1,L2,P,Q,MA,MC; 19 20 int main() 21 { 22 int T;scanf("%d",&T); 23 for(;T--;) 24 { 25 scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y); 26 if(A.y==B.y || C.y==D.y){ printf("0.00\n");continue; } 27 if(A.y<B.y) swap(A,B); 28 if(C.y<D.y) swap(C,D); 29 double a=(C-A) * (D-A),b = (D-B) * (C-B); 30 if(a*b<-eps){ printf("0.00\n"); continue;} 31 P=(B-A) * (a / (a+b)) + A; 32 if(P.y>C.y || P.y<D.y){ printf("0.00\n");continue; } 33 if(A.y>C.y) 34 { 35 Q=B + (A-B) * ((C.x-B.x)/(A.x-B.x)); 36 if(Q.y>=C.y && A.y>=Q.y){ printf("0.00\n");continue;} 37 MA=B + (A-B) * ((C.y-B.y)/(A.y-B.y)); 38 printf("%.2lf\n",fabs((MA-P) * (C-P) / 2)); 39 } 40 else 41 { 42 Q=D + (C-D) * ((A.x-D.x)/(C.x-D.x)); 43 if(Q.y>=A.y && C.y>=Q.y){ printf("0.00\n");continue; } 44 MC=D+(C-D) * ((A.y-D.y) / (C.y-D.y)); 45 printf("%.2lf\n",fabs((MC-P) * (A-P) / 2) ); 46 } 47 } 48 }
1 //https://blog.csdn.net/qq_16657927/article/details/79942140 2 /* 3 |16/11/06ztx| 4 */ 5 6 struct node { 7 double x; // 横坐标 8 double y; // 纵坐标 9 }; 10 11 typedef node Vector; 12 13 Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } 14 Vector operator - (Point A, Point B) { return Vector(A.x - B.y, A.y - B.y); } 15 Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } 16 Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y*p); } 17 18 double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } // 向量点乘 19 double Length(Vector A) { return sqrt(Dot(A, A)); } // 向量模长 20 double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); } // 向量之间夹角 21 22 double Cross(Vector A, Vector B) { // 叉积计算 公式 23 return A.x*B.y - A.y*B.x; 24 } 25 26 Vector Rotate(Vector A, double rad) // 向量旋转 公式 { 27 return Vector(A.x*cos(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad)); 28 } 29 30 Point getLineIntersection(Point P, Vector v, Point Q, Vector w) { // 两直线交点t1 t2计算公式 31 Vector u = P - Q; 32 double t = Cross(w, u) / Cross(v, w); // 求得是横坐标 33 return P + v*t; // 返回一个点 34 }
3.3 求多边形面积
1 /* 2 |16/11/06ztx| 3 */ 4 5 node G[maxn]; 6 int n; 7 8 double Cross(node a, node b) { // 叉积计算 9 return a.x*b.y - a.y*b.x; 10 } 11 12 13 int main() 14 { 15 while (scanf("%d", &n) != EOF && n) { 16 for (int i = 0; i < n; i++) 17 scanf("%lf %lf", &G[i].x, &G[i].y); 18 double sum = 0; 19 G[n].x = G[0].x; 20 G[n].y = G[0].y; 21 for (int i = 0; i < n; i++) { 22 sum += Cross(G[i], G[i + 1]); 23 } 24 // 或者 25 //for (int i = 0; i < n; i++) { 26 //sum += fun(G[i], G[（i + 1）% n]); 27 //} 28 sum = sum / 2.0; 29 printf("%.1f\n", sum); 30 } 31 system("pause"); 32 return 0; 33 }
3.4 判断直线相交
1 /* 2 |16/11/06ztx| 3 */ 4 5 node P[35][105]; 6 7 double Cross_Prouct(node A,node B,node C) { // 计算BA叉乘CA 8 return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); 9 } 10 bool Intersect(node A,node B,node C,node D) { // 通过叉乘判断线段是否相交； 11 if(min(A.x,B.x)<=max(C.x,D.x)&& // 快速排斥实验； 12 min(C.x,D.x)<=max(A.x,B.x)&& 13 min(A.y,B.y)<=max(C.y,D.y)&& 14 min(C.y,D.y)<=max(A.y,B.y)&& 15 Cross_Prouct(A,B,C)*Cross_Prouct(A,B,D)<0&& // 跨立实验； 16 Cross_Prouct(C,D,A)*Cross_Prouct(C,D,B)<0) // 叉乘异号表示在两侧； 17 return true; 18 else return false; 19 }
3.5 凸包
1 /* 2 向量叉积判断多边形凹凸 3 4 对于连续的三个点p0,p1,p2，另向量a=p1-p0，b=p2-p1若是凸多边形，那么b相对于a一定是向逆时针方向 5 6 旋转的。 7 8 判断两向量的旋转方向，可以使用向量的叉积 a×b ＝ x1×y2 － x2×y1 9 10 a×b > 0 b在a的逆时针方向 11 a×b = 0 b平行于a（共线） 12 a×b < 0 b在a的顺时针方向 13 14 要注意的是，对于最后一个点pn，还要和起始的两个点p0,p1判断一次。 15 */ 16 17 18 #include <cstdio> 19 #include <cmath> 20 #include <cstdlib> 21 #include <algorithm> 22 #define eps 1e-8 23 #define MAXN 110 24 using namespace std; 25 struct Point 26 { 27 double x, y; 28 Point(){} 29 Point(double X, double Y){ 30 x = X; y = Y; 31 } 32 }; 33 Point P[MAXN]; 34 int dcmp(double x) 35 { 36 if(fabs(x) < eps) 37 return 0; 38 else 39 return x < 0 ? -1 : 1; 40 } 41 Point operator - (Point A, Point B){ 42 return Point(A.x-B.x, A.y-B.y); 43 } 44 Point operator + (Point A, Point B){ 45 return Point(A.x+B.x, A.y+B.y); 46 } 47 Point operator * (Point A, double p){ 48 return Point(A.x*p, A.y*p);; 49 } 50 double Cross(Point A, Point B){ 51 return A.x*B.y - A.y*B.x; 52 } 53 double Dot(Point A, Point B){ 54 return A.x*B.x + A.y*B.y; 55 } 56 double Dis(Point A, Point B){ 57 return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y)); 58 } 59 bool operator == (Point A, Point B){ 60 return dcmp(A.x-B.x) == 0 && dcmp(A.y-B.y) == 0; 61 } 62 bool cmp(Point A, Point B)//按极角升序排序，若角度相等距离小的在前面 63 { 64 double temp = Cross(A-P[0], B-P[0]); 65 if(dcmp(temp) > 0) return true; 66 if(dcmp(temp) == 0 && dcmp(Dis(P[0], A) - Dis(P[0], B)) < 0) return true; 67 return false; 68 } 69 int Stack[MAXN], top;//下标从0开始计数到top 70 void input(int n) 71 { 72 scanf("%lf%lf", &P[0].x, &P[0].y); 73 double xx = P[0].x, yy = P[0].y; 74 int id = 0;//找到y坐标最小的点，若有多个选择x坐标最小的记录下标 75 for(int i = 1; i < n; i++) 76 { 77 scanf("%lf%lf", &P[i].x, &P[i].y); 78 if(P[i].y < yy || (P[i].y == yy && P[i].x < xx)) 79 { 80 xx = P[i].x; 81 yy = P[i].y; 82 id = i; 83 } 84 } 85 Point T; 86 T = P[0]; P[0] = P[id]; P[id] = T; 87 sort(P+1, P+n, cmp);//极角排序 88 } 89 void Graham(int n) 90 { 91 if(n == 1){ top = 0; Stack[0] = 0;} 92 else if(n == 2) 93 { 94 top = 1; 95 Stack[0] = 0; 96 Stack[1] = 1; 97 } 98 else 99 { 100 for(int i = 0; i <= 1; i++) 101 Stack[i] = i; 102 top = 1; 103 for(int i = 2; i < n; i++) 104 { //如果和上一条边成左旋关系，压栈继续；反之一直弹栈直到和栈顶两点的边成左转关系，压栈继续。 105 while(top > 0 && dcmp(Cross(P[Stack[top]]-P[Stack[top-1]], P[i]-P[Stack[top-1]])) <= 0) top--; 106 top++; 107 Stack[top] = i; 108 } 109 } 110 } 111 int main() 112 { 113 int n; 114 input(n); 115 Graham(n); 116 return 0; 117 }
四.技巧
4.1 imos累积和法
1 //http://www.hankcs.com/program/algorithm/imos_method.html 2 //算法用于计算二维平面最大高度点，原理左上右下标1，左下右上标-1，累加求最大。 3 #include <iostream> 4 #include <algorithm> 5 #include <bits/stdc++.h> 6 using namespace std; 7 #define W 6 8 #define H 6 9 #define N 4 10 // 左下角坐标 11 int B[N] = {3,4,3,5,}; 12 int C[N] = {0,1,2,2,}; 13 // 右上角坐标 14 int A[N] = {0,3,2,2,}; 15 int D[N] = {3,2,3,5,}; 16 // 地图上的分布结果 17 int tiles[H][W]; 18 19 ///////////////////////////SubMain////////////////////////////////// 20 int main(int argc, char *argv[]) 21 { 22 memset(tiles, 0, sizeof(tiles)); 23 // 影响力计算 (图 3) 24 for (int i = 0; i < N; i++) 25 { 26 tiles[C[i]][A[i]]++; 27 tiles[C[i]][B[i]]--; 28 tiles[D[i]][A[i]]--; 29 tiles[D[i]][B[i]]++; 30 } 31 // 横向累积和 (图 4, 5) 32 for (int y = 0; y < H; y++) 33 { 34 for (int x = 1; x < W; x++) 35 { 36 tiles[y][x] += tiles[y][x - 1]; 37 } 38 } 39 // 纵向累积和 (图 6, 7) 40 for (int y = 1; y < H; y++) 41 { 42 for (int x = 0; x < W; x++) 43 { 44 tiles[y][x] += tiles[y - 1][x]; 45 } 46 } 47 48 cout << *max_element(tiles[0], tiles[0] + H * W) << endl; 49 system("pause"); 50 return 0; 51 } 52 ///////////////////////////End Sub//////////////////////////////////
4.2 坐标离散化
1 //http://www.hankcs.com/program/algorithm/aoj-0531-paint-color.html 2 #include<iostream> 3 #include<vector> 4 #include<algorithm> 5 #include<queue> 6 #include <cstring> 7 #define MAX_N 1000 + 16 8 9 using namespace std; 10 11 int N, H, W; 12 int X1[MAX_N], X2[MAX_N], Y1[MAX_N], Y2[MAX_N]; 13 int fld[2 * MAX_N][2 * MAX_N], // 填充遍历用，代表坐标(i, j)处是否空白（压缩后） 14 dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 }; 15 16 // 压缩坐标，将坐标的值变成“这是第几种值”，返回一共有几种坐标 17 int compress(int *x1, int *x2, int w) 18 { 19 vector<int>xs; 20 21 for (int i = 0; i < N; ++i) 22 { 23 int tx1 = x1[i], tx2 = x2[i]; 24 if (1 <= tx1 && tx1 < w) xs.push_back(tx1); 25 if (1 <= tx2 && tx2 < w) xs.push_back(tx2); 26 } 27 xs.push_back(0); 28 xs.push_back(w); 29 sort(xs.begin(), xs.end()); 30 xs.erase(unique(xs.begin(), xs.end()), xs.end()); 31 for (int i = 0; i < N; ++i) 32 { 33 x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin(); 34 x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin(); 35 } 36 return xs.size() - 1; 37 } 38 39 int bfs() 40 { 41 int ans = 0; 42 for (int i = 0; i < H; ++i) 43 { 44 for (int j = 0; j < W; ++j) 45 { 46 if (fld[i][j]) continue; 47 ++ans; 48 queue<pair<int, int> >que; 49 que.push(make_pair(j, i)); 50 while (!que.empty()) 51 { 52 int nx = que.front().first, ny = que.front().second; 53 que.pop(); 54 55 for (int i = 0; i < 4; ++i) 56 { 57 int tx = nx + dx[i], ty = ny + dy[i]; 58 if (tx < 0 || W < tx || ty < 0 || H< ty || fld[ty][tx] > 0) continue; 59 que.push(make_pair(tx, ty)); 60 fld[ty][tx] = 1; 61 } 62 } 63 } 64 } 65 return ans; 66 } 67 68 ///////////////////////////SubMain////////////////////////////////// 69 int main(int argc, char *argv[]) 70 { 71 while (cin >> W >> H, W | H) 72 { 73 cin >> N; 74 for (int i = 0; i < N; ++i) 75 { 76 cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i]; 77 } 78 79 memset(fld, 0, sizeof(fld)); 80 81 W = compress(X1, X2, W); 82 H = compress(Y1, Y2, H); 83 84 // imos-法 85 for (int i = 0; i < N; i++) 86 { 87 fld[Y1[i]][X1[i]]++; 88 fld[Y1[i]][X2[i]]--; 89 fld[Y2[i]][X1[i]]--; 90 fld[Y2[i]][X2[i]]++; 91 } 92 // 横向累积 93 for (int i = 0; i < H; i++) 94 { 95 for (int j = 1; j < W; j++) 96 { 97 fld[i][j] += fld[i][j - 1]; 98 } 99 } 100 // 纵向累积 101 for (int i = 1; i < H; i++) 102 { 103 for (int j = 0; j < W; j++) 104 { 105 fld[i][j] += fld[i - 1][j]; 106 } 107 }// 累积完后，fld中非0部分表示有挡板 108 cout << bfs() << endl; 109 } 110 return 0; 111 } 112 ///////////////////////////End Sub//////////////////////////////////
4.3 博弈sg模板
1 //f[]：可以取走的石子个数 2 //sg[]:0~n的SG函数值 3 //hash[]:mex{} 4 int f[N],sg[N],hash[N]; 5 void getSG(int n) 6 { 7 int i,j; 8 memset(sg,0,sizeof(sg)); 9 for(i=1;i<=n;i++) 10 { 11 memset(hash,0,sizeof(hash)); 12 for(j=1;f[j]<=i;j++) 13 hash[sg[i-f[j]]]=1; 14 for(j=0;j<=n;j++) //求mes{}中未出现的最小的非负整数 15 { 16 if(hash[j]==0) 17 { 18 sg[i]=j; 19 break; 20 } 21 } 22 } 23 }
1 //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍 2 //n是集合s的大小 S[i]是定义的特殊取法规则的数组 3 int s[110],sg[10010],n; 4 int SG_dfs(int x) 5 { 6 int i; 7 if(sg[x]!=-1) 8 return sg[x]; 9 bool vis[110]; 10 memset(vis,0,sizeof(vis)); 11 for(i=0;i<n;i++) 12 { 13 if(x>=s[i]) 14 { 15 SG_dfs(x-s[i]); 16 vis[sg[x-s[i]]]=1; 17 } 18 } 19 int e; 20 for(i=0;;i++) 21 if(!vis[i]) 22 { 23 e=i; 24 break; 25 } 26 return sg[x]=e; 27 }
五.数据结构
5.1 并查集
1 //https://blog.csdn.net/u013486414/article/details/38682057 2 const int MAXSIZE = 500; 3 4 int uset[MAXSIZE]; 5 6 int rank[MAXSIZE]; 7 8 9 10 void makeSet(int size) { 11 12 for(int i = 0;i < size;i++) uset[i] = i; 13 14 for(int i = 0;i < size;i++) rank[i] = 0; 15 16 } 17 18 int find(int x) { 19 20 if (x != uset[x]) uset[x] = find(uset[x]); 21 22 return uset[x]; 23 24 } 25 26 void unionSet(int x, int y) { 27 28 if ((x = find(x)) == (y = find(y))) return; 29 30 if (rank[x] > rank[y]) uset[y] = x; 31 32 else { 33 34 uset[x] = y; 35 36 if (rank[x] == rank[y]) rank[y]++; 37 38 } 39 40 }
5.2 求图中任意两点的最短距离的 弗洛伊德算法
1 //https://blog.csdn.net/qq_16657927/article/details/79942140 2 /* 3 |Floyd算法| 4 |任意点对最短路算法| 5 |求图中任意两点的最短距离的算法| 6 */ 7 8 for (int k = 0; k < n; k++) { 9 for (int i = 0; i < n; i++) { 10 for (int j = 0; j < n; j++) { 11 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); 12 } 13 } 14 }
5.3 最小生成树·Kruskal
1 //https://blog.csdn.net/qq_16657927/article/details/79942140 2 /* 3 |Kruskal算法| 4 |适用于 稀疏图 求最小生成树| 5 |16/11/05ztx thanks to wangqiqi| 6 */ 7 8 /* 9 第一步：点、边、加入vector，把所有边按从小到大排序 10 第二步：并查集部分 + 下面的code 11 */ 12 13 void Kruskal() { 14 ans = 0; 15 for (int i = 0; i<len; i++) { 16 if (Find(edge[i].a) != Find(edge[i].b)) { 17 Union(edge[i].a, edge[i].b); 18 ans += edge[i].len; 19 } 20 } 21 }
5.4 最小生成树· prim算法
1 //https://blog.csdn.net/qq_16657927/article/details/79942140 2 /* 3 |Prim算法| 4 |适用于 稠密图 求最小生成树| 5 |堆优化版，时间复杂度：O(elgn)| 6 |16/11/05ztx, thanks to chaixiaojun| 7 */ 8 9 struct node { 10 int v, len; 11 node(int v = 0, int len = 0) :v(v), len(len) {} 12 bool operator < (const node &a)const { // 加入队列的元素自动按距离从小到大排序 13 return len> a.len; 14 } 15 }; 16 17 vector<node> G[maxn]; 18 int vis[maxn]; 19 int dis[maxn]; 20 21 void init() { 22 for (int i = 0; i<maxn; i++) { 23 G[i].clear(); 24 dis[i] = INF; 25 vis[i] = false; 26 } 27 } 28 int Prim(int s) { 29 priority_queue<node>Q; // 定义优先队列 30 int ans = 0; 31 Q.push(node(s,0)); // 起点加入队列 32 while (!Q.empty()) { 33 node now = Q.top(); Q.pop(); // 取出距离最小的点 34 int v = now.v; 35 if (vis[v]) continue; // 同一个节点，可能会推入2次或2次以上队列，这样第一个被标记后，剩下的需要直接跳过。 36 vis[v] = true; // 标记一下 37 ans += now.len; 38 for (int i = 0; i<G[v].size(); i++) { // 开始更新 39 int v2 = G[v][i].v; 40 int len = G[v][i].len; 41 if (!vis[v2] && dis[v2] > len) { 42 dis[v2] = len; 43 Q.push(node(v2, dis[v2])); // 更新的点加入队列并排序 44 } 45 } 46 } 47 return ans; 48 }
1 //https://blog.csdn.net/qq_16657927/article/details/79942140 2 #include<iostream> 3 #include<string> 4 #include<vector> 5 using namespace std; 6 7 //首先是使用邻接矩阵完成Prim算法 8 struct Graph { 9 int vexnum; //顶点个数 10 int edge; //边的条数 11 int ** arc; //邻接矩阵 12 string *information; //记录每个顶点名称 13 }; 14 15 //创建图 16 void createGraph(Graph & g) { 17 cout << "请输入顶点数：输入边的条数" << endl; 18 cin >> g.vexnum; 19 cin >> g.edge; //输入边的条数 20 21 g.information = new string[g.vexnum]; 22 g.arc = new int*[g.vexnum]; 23 int i = 0; 24 25 //开辟空间的同时，进行名称的初始化 26 for (i = 0; i < g.vexnum; i++) { 27 g.arc[i] = new int[g.vexnum]; 28 g.information[i]="v"+ std::to_string(i+1);//对每个顶点进行命名 29 for (int k = 0; k < g.vexnum; k++) { 30 g.arc[i][k] = INT_MAX; //初始化我们的邻接矩阵 31 } 32 } 33 34 cout << "请输入每条边之间的顶点编号(顶点编号从1开始),以及该边的权重：" << endl; 35 for (i = 0; i < g.edge; i++) { 36 int start; 37 int end; 38 cin >> start; //输入每条边的起点 39 cin >> end; //输入每条边的终点 40 int weight; 41 cin >> weight; 42 g.arc[start-1][end-1]=weight;//无向图的边是相反的 43 g.arc[end-1][start-1] = weight; 44 } 45 } 46 47 //打印图 48 void print(Graph g) { 49 int i; 50 for (i = 0; i < g.vexnum; i++) { 51 //cout << g.information[i] << " "; 52 for (int j = 0; j < g.vexnum; j++) { 53 if (g.arc[i][j] == INT_MAX) 54 cout << "∞" << " "; 55 else 56 cout << g.arc[i][j] << " "; 57 } 58 cout << endl; 59 } 60 } 61 62 //作为记录边的信息，这些边都是达到end的所有边中，权重最小的那个 63 struct Assis_array { 64 int start; //边的终点 65 int end; //边的起点 66 int weight; //边的权重 67 }; 68 //进行prim算法实现，使用的邻接矩阵的方法实现。 69 void Prim(Graph g,int begin) { 70 71 //close_edge这个数组记录到达某个顶点的各个边中的权重最大的那个边 72 Assis_array *close_edge=new Assis_array[g.vexnum]; 73 74 int j; 75 76 //进行close_edge的初始化，更加开始起点进行初始化 77 for (j = 0; j < g.vexnum; j++) { 78 if (j != begin - 1) { 79 close_edge[j].start = begin-1; 80 close_edge[j].end = j; 81 close_edge[j].weight = g.arc[begin - 1][j]; 82 } 83 } 84 //把起点的close_edge中的值设置为-1，代表已经加入到集合U了 85 close_edge[begin - 1].weight = -1; 86 //访问剩下的顶点，并加入依次加入到集合U 87 for (j = 1; j < g.vexnum; j++) { 88 89 int min = INT_MAX; 90 int k; 91 int index; 92 //寻找数组close_edge中权重最小的那个边 93 for (k = 0; k < g.vexnum; k++) { 94 if (close_edge[k].weight != -1) { 95 if (close_edge[k].weight < min) { 96 min = close_edge[k].weight; 97 index = k; 98 } 99 } 100 } 101 //将权重最小的那条边的终点也加入到集合U 102 close_edge[index].weight = -1; 103 //输出对应的边的信息 104 cout << g.information[close_edge[index].start] 105 << "-----" 106 << g.information[close_edge[index].end] 107 << "=" 108 <<g.arc[close_edge[index].start][close_edge[index].end] 109 <<endl; 110 111 //更新我们的close_edge数组。 112 for (k = 0; k < g.vexnum; k++) { 113 if (g.arc[close_edge[index].end][k] <close_edge[k].weight) { 114 close_edge[k].weight = g.arc[close_edge[index].end][k]; 115 close_edge[k].start = close_edge[index].end; 116 close_edge[k].end = k; 117 } 118 } 119 } 120 } 121 122 123 124 int main() 125 { 126 Graph g; 127 createGraph(g);//基本都是无向网图，所以我们只实现了无向网图 128 print(g); 129 Prim(g, 1); 130 system("pause"); 131 return 0; 132 }
5.5 染色法
1 /* 2 |交叉染色法判断二分图| 3 |16/11/05ztx| 4 */ 5 6 int bipartite(int s) { 7 int u, v; 8 queue<int>Q; 9 color[s] = 1; 10 Q.push(s); 11 while (!Q.empty()) { 12 u = Q.front(); 13 Q.pop(); 14 for (int i = 0; i < G[u].size(); i++) { 15 v = G[u][i]; 16 if (color[v] == 0) { 17 color[v] = -color[u]; 18 Q.push(v); 19 } 20 else if (color[v] == color[u]) 21 return 0; 22 } 23 } 24 return 1; 25 }
5.6 匈牙利算法
1 //https://blog.csdn.net/qq_16657927/article/details/79942140 2 /* 3 |求解最大匹配问题| 4 |递归实现| 5 |16/11/05ztx| 6 */ 7 8 vector<int>G[maxn]; 9 bool inpath[maxn]; // 标记 10 int match[maxn]; // 记录匹配对象 11 void init() 12 { 13 memset(match, -1, sizeof(match)); 14 for (int i = 0; i < maxn; ++i) { 15 G[i].clear(); 16 } 17 } 18 bool findpath(int k) { 19 for (int i = 0; i < G[k].size(); ++i) { 20 int v = G[k][i]; 21 if (!inpath[v]) { 22 inpath[v] = true; 23 if (match[v] == -1 || findpath(match[v])) { // 递归 24 match[v] = k; // 即匹配对象是“k妹子”的 25 return true; 26 } 27 } 28 } 29 return false; 30 } 31 32 void hungary() { 33 int cnt = 0; 34 for (int i = 1; i <= m; i++) { // m为需要匹配的“妹子”数 35 memset(inpath, false, sizeof(inpath)); // 每次都要初始化 36 if (findpath(i)) cnt++; 37 } 38 cout << cnt << endl; 39 }
1 /* 2 |求解最大匹配问题| 3 |dfs实现| 4 |16/11/05ztx| 5 */ 6 7 int v1, v2; 8 bool Map[501][501]; 9 bool visit[501]; 10 int link[501]; 11 int result; 12 13 bool dfs(int x) { 14 for (int y = 1; y <= v2; ++y) { 15 if (Map[x][y] && !visit[y]) { 16 visit[y] = true; 17 if (link[y] == 0 || dfs(link[y])) { 18 link[y] = x; 19 return true; 20 } } } 21 return false; 22 } 23 24 25 void Search() { 26 for (int x = 1; x <= v1; x++) { 27 memset(visit,false,sizeof(visit)); 28 if (dfs(x)) 29 result++; 30 } 31 }
5.7 Dijstra算法
1 //https://blog.csdn.net/mengxiang000000/article/details/50421243 2 #include<stdio.h> 3 #include<string.h> 4 #include<iostream> 5 using namespace std; 6 #define N 0x1f1f1f1f 7 int w[151][151]; 8 int d[155]; 9 int ans,vis[151]; 10 int n,m; 11 void Dij() 12 { 13 int i,j,k,v,tmp; 14 memset(vis,0,sizeof(vis)); 15 for(i=1;i<=n;i++) 16 d[i]=w[1][i]; 17 d[1]=0; 18 vis[1]=1; 19 for(i=1;i<=n;i++) 20 { 21 tmp=N; 22 for(j=1;j<=n;j++) 23 { 24 if(tmp>d[j]&&!vis[j]) 25 { 26 tmp=d[j]; 27 v=j; 28 } 29 } 30 vis[v]=1; 31 for(k=1;k<=n;k++) 32 { 33 if(!vis[k]) 34 d[k]=min(d[k],d[v]+w[v][k]); 35 } 36 } 37 } 38 int main() 39 { 40 while(~scanf("%d%d",&n,&m)) 41 { 42 if(n==0&&m==0)break; 43 for(int i=1;i<=n;i++) 44 { 45 for(int j=1;j<=n;j++) 46 { 47 w[i][j]=0x1f1f1f1f; 48 } 49 } 50 for(int i=0;i<m;i++) 51 { 52 int a,b,dis; 53 scanf("%d%d%d",&a,&b,&dis); 54 if(w[a][b]>dis) 55 w[a][b]=w[b][a]=dis; 56 } 57 Dij(); 58 printf("%d\n",d[n]); 59 } 60 }
5.8 Bellman-ford算法
1 struct edge{int from,to,cost;}; 2 3 edge es[MAX_E]; 4 5 int d[MAX_V]; 6 int V,E; 7 8 void shortest(int k){ 9 memset(d,0x3f,sizeof(d)); 10 d[k]=0; 11 while(true){ 12 bool update=false; 13 for(int i=0;i<E;i++){ 14 edge e=es[i]; 15 if(d[e.from]!=INF&&d[e.from]+e.cost<d[e.to]){ 16 d[e.to]=d[e.from]+e.cost; 17 update=true; 18 } 19 } 20 if(!update)break; 21 } 22 }
5.9 字典树
1 /******************************************************************************* 2 3 【字典树】 4 5 此模板主要是针对都是小写字母的。其他情况在此基础上改一改就可以了，要懂得灵活运用。 6 7 ********************************************************************************/ 8 9 struct trie /*字典树的节点内容*/ 10 { 11 int count;/*计算该节点出现的次数*/ 12 trie *next[26];/*一个节点有26个指针（孩子），即'a'-'z'*/ 13 }; 14 15 trie *root; 16 17 trie* newtrie()/*建立一个节点。（也可以用建立个大的数组，指针指向数组不同位置）*/ 18 { 19 trie *t; 20 t=(trie*)malloc(sizeof(struct trie)); 21 memset(t,0,sizeof(struct trie)); 22 return t; 23 } 24 25 void Insert(char *ch) /*插入函数，将该字符串插入到字典树中 */ 26 { 27 int i; 28 trie *t,*s; 29 s=root; 30 for(i=0;ch[i];i++) 31 { 32 if(s->next[ch[i]-'a']) 33 { 34 s=s->next[ch[i]-'a']; 35 s->count=s->count+1; 36 } 37 else 38 { 39 t=newtrie(); 40 s->next[ch[i]-'a']=t; 41 s=t; 42 s->count=1; 43 } 44 } 45 } 46 47 int Search(char *ch)/*搜索函数，返回0则代表字典树不存在该字符串，反之亦然 */ 48 { 49 int i; 50 trie *s=root; 51 if(ch[0]==0) return 0; 52 for(i=0;ch[i];i++) 53 { 54 if(s->next[ch[i]-'a']) 55 s=s->next[ch[i]-'a']; 56 else 57 break; 58 } 59 if(ch[i]==0) return s->count; 60 else return 0; 61 } 62 63 void Delete(char *ch)/*删除函数，将该字符串从字典树中删除（删除之前记得事先判断存不存在该字符串）*/ 64 { 65 int i; 66 trie *s; 67 s=root; 68 for(i=0;ch[i];i++) 69 { 70 s=s->next[ch[i]-'a']; 71 s->count=s->count-1; 72 } 73 }
5.10 AC自动机
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<algorithm> 7 #define il inline 8 #define RG register 9 #define N 10010 10 using namespace std; 11 12 char s[N][55],ss[N*100]; 13 int n,times[N];//times记录单词在文本串中出现的次数 14 15 struct Trie{ 16 int son[N][26],fail[N],root,L,num[N]; 17 int last[N];//只是一个优化，有没有都没关系 18 19 void init(){ 20 L=1; root=0; 21 memset(son,0,sizeof(son)); 22 memset(num,0,sizeof(num)); 23 memset(last,0,sizeof(last)); 24 memset(fail,0,sizeof(fail)); 25 } 26 27 il int idx(char c){ return c-'a'; } 28 29 void insert( char s[],int v ){ 30 int len=strlen(s), cur=root; 31 for(int i=0;i<len;i++){ 32 int id=idx(s[i]); 33 if(!son[cur][id]) 34 son[cur][id]=L++; 35 cur=son[cur][id]; 36 } 37 num[cur]=v; //记录单词编号 38 } 39 40 void build(){ 41 int que[N],hd=0,tl=0; 42 for(int i=0;i<26;i++) 43 if(son[root][i]){ 44 que[tl++]=son[root][i]; 45 fail[son[root][i]]=root; 46 } 47 else son[root][i]=root; 48 49 while(hd<tl){ 50 int cur=que[hd++]; 51 for(int i=0;i<26;i++){ 52 int Son=son[cur][i]; 53 if(Son){ 54 int f=fail[cur]; 55 while(f && !son[f][i]) f=fail[f]; 56 fail[Son]=son[f][i]; 57 num[Son]=num[fail[Son]];//不用last优化时要加上这一句 58 que[tl++]=Son; 59 } 60 else son[cur][i]=son[fail[cur]][i]; 61 } 62 //if( num[fail[cur]] )last[cur]=fail[cur]; 63 //else last[cur]=last[fail[cur]]; 64 } 65 } 66 67 void query( char s[] ){ 68 int len=strlen(s),cur=root; 69 for(int i=0;i<len;i++){ 70 int id=idx(s[i]); 71 while(cur && !son[cur][id]) cur=fail[cur]; 72 if(son[cur][id]){ 73 cur=son[cur][id]; 74 int k=cur; 75 while(k) times[ num[k] ]++,k=fail[k]; 76 /*while(k){ 77 if(num[k]) times[num[k]]++; 78 k=last[k]; 79 }*/ 80 } 81 82 } 83 } 84 85 }AC; 86 87 int main(){ 88 scanf("%d",&n); AC.init(); 89 for(RG int i = 1;i<=n;i++){ 90 scanf("%s",s[i]); 91 AC.insert(s[i],i); 92 } 93 AC.build(); 94 scanf("%s",ss); AC.query(ss); 95 for( RG int i=1;i<=n;i++ ) printf("%s %d\n",s[i],times[i]); 96 return 0; 97 }
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 struct Node 5 { 6 int cnt;//是否为该单词的最后一个结点 7 Node *fail;//失败指针 8 Node *next[26];//Trie中每个结点的各个节点 9 }*queue[500005];//队列，方便用BFS构造失败指针 10 char s[1000005];//主字符串 11 char keyword[55];//需要查找的单词 12 Node *root;//头结点 13 void Init(Node *root)//每个结点的初始化 14 { 15 root->cnt=0; 16 root->fail=NULL; 17 for(int i=0;i<26;i++) 18 root->next[i]=NULL; 19 } 20 void Build_trie(char *keyword)//构建Trie树 21 { 22 Node *p,*q; 23 int i,v; 24 int len=strlen(keyword); 25 for(i=0,p=root;i<len;i++) 26 { 27 v=keyword[i]-'a'; 28 if(p->next[v]==NULL) 29 { 30 q=(struct Node *)malloc(sizeof(Node)); 31 Init(q); 32 p->next[v]=q;//结点链接 33 } 34 p=p->next[v];//指针移动到下一个结点 35 } 36 p->cnt++;//单词最后一个结点cnt++，代表一个单词 37 } 38 void Build_AC_automation(Node *root) 39 { 40 int head=0,tail=0;//队列头、尾指针 41 queue[head++]=root;//先将root入队 42 while(head!=tail) 43 { 44 Node *p=NULL; 45 Node *temp=queue[tail++];//弹出队头结点 46 for(int i=0;i<26;i++) 47 { 48 if(temp->next[i]!=NULL)//找到实际存在的字符结点 49 { //temp->next[i] 为该结点，temp为其父结点 50 if(temp==root)//若是第一层中的字符结点，则把该结点的失败指针指向root 51 temp->next[i]->fail=root; 52 else 53 { 54 //依次回溯该节点的父节点的失败指针直到某节点的next[i]与该节点相同， 55 //则把该节点的失败指针指向该next[i]节点； 56 //若回溯到 root 都没有找到，则该节点的失败指针指向 root 57 p=temp->fail;//将该结点的父结点的失败指针给p 58 while(p!=NULL) 59 { 60 if(p->next[i]!=NULL) 61 { 62 temp->next[i]->fail=p->next[i]; 63 break; 64 } 65 p=p->fail; 66 } 67 //让该结点的失败指针也指向root 68 if(p==NULL) 69 temp->next[i]->fail=root; 70 } 71 queue[head++]=temp->next[i];//每处理一个结点，都让该结点的所有孩子依次入队 72 } 73 } 74 } 75 } 76 int query(Node *root) 77 { //i为主串指针，p为模式串指针 78 int i,v,count=0; 79 Node *p=root; 80 int len=strlen(s); 81 for(i=0;i<len;i++) 82 { 83 v=s[i]-'a'; 84 //由失败指针回溯查找，判断s[i]是否存在于Trie树中 85 while(p->next[v]==NULL && p!=root) 86 p=p->fail; 87 p=p->next[v];//找到后p指针指向该结点 88 if(p==NULL)//若指针返回为空，则没有找到与之匹配的字符 89 p=root; 90 Node *temp=p;//匹配该结点后，沿其失败指针回溯，判断其它结点是否匹配 91 while(temp!=root)//匹配结束控制 92 { 93 if(temp->cnt>=0)//判断该结点是否被访问 94 { 95 count+=temp->cnt;//由于cnt初始化为 0，所以只有cnt>0时才统计了单词的个数 96 temp->cnt=-1;//标记已访问过 97 } 98 else//结点已访问，退出循环 99 break; 100 temp=temp->fail;//回溯 失败指针 继续寻找下一个满足条件的结点 101 } 102 } 103 return count; 104 } 105 int main() 106 { 107 int T,n; 108 scanf("%d",&T); 109 while(T--) 110 { 111 root=(struct Node *)malloc(sizeof(Node)); 112 Init(root); 113 scanf("%d",&n); 114 for(int i=0;i<n;i++) 115 { 116 scanf("\n%s",keyword); 117 Build_trie(keyword); 118 } 119 Build_AC_automation(root); 120 scanf("\n%s",s); 121 printf("%d\n",query(root)); 122 } 123 return 0; 124 }
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
相关文章
- C++冒泡排序 （基于函数模板实现） 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- Unsolved --> Solved OJ思路题解 2020-05-30
- C++ 模板类vector 2020-05-30
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签