Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- expt1
- #include<stdio.h>
- #include<stdlib.h>
- #include<time.h>
- #define len 100000
- double selectionsort(int a[],long int n)
- {
- long int i,j,pos;
- int min;
- clock_t t1,t2;
- double time_elapsed;
- t1=clock();
- for(i=0;i<n;i++)
- {
- min=a[i];
- pos=i;
- for(j=i+1;j<n;j++)
- {
- if(min>a[j])
- {
- min=a[j];
- pos=j;
- }
- }
- a[pos]=a[i];
- a[i]=min;
- }
- t2=clock();
- time_elapsed=(double)(t2-t1)/CLOCKS_PER_SEC; //time elapsed for selection sort
- return time_elapsed;
- }
- double insertionsort(int a[],long int n)
- {
- long int i,j;int temp;
- clock_t t1,t2;
- double time_elapsed;
- t1=clock();
- for(j=1;j<n;j++)
- {
- i=j-1;
- temp=a[j];
- while(i>=0 && a[i]>temp)
- {
- a[i+1]=a[i];
- i--;
- }
- a[i+1]=temp;
- }
- t2=clock();
- time_elapsed=(double)(t2-t1)/CLOCKS_PER_SEC; //time elapsed for insertion sort
- return time_elapsed;
- }
- void dataread(int a[])
- {
- long int i;
- FILE *fp;
- fp=fopen("data.txt","r");
- for(i=0;i<len;i++)
- {
- fscanf(fp,"%d",&a[i]);
- }
- fclose(fp);
- }
- int main(void)
- {
- int a[len],nextrand;
- long int i;
- FILE *fp;
- fp=fopen("data.txt","w");
- for(i=0;i<len;i++)
- {
- nextrand=rand()%100;
- fprintf(fp,"%d\n",nextrand);
- }
- fclose(fp);
- printf("\t\t Insertion\t Selection\n");
- for(i=10;i<=len;i=i*10) //multiples of 10 number of integers starting from 10
- {
- printf("%ld integers",i);
- dataread(a);
- printf("\t%.9lf\t",insertionsort(a,i));
- printf("\t%.9lf",insertionsort(a,i));
- printf("\n");
- }
- return 0;
- }
- expt2
- #include <stdio.h>
- #include <stdlib.h>
- #include<time.h>
- #define len 250000
- void merge(int a[],long int lb, long int m, long int ub)
- {
- int temp[len];
- long int i,j,k;
- i=lb;
- j = m+1;
- k = 0;
- while(i<=m && j<=ub)
- if (a[i]<a[j])
- temp[k++] = a[i++];
- else temp[k++] = a[j++];
- while (i<=m)
- temp[k++] = a[i++];
- while (j<=ub)
- temp[k++] = a[j++];
- k=0;
- for (i=lb; i<=ub; i++)
- a[i] = temp[k++];
- return;
- }
- void mergesort(int a[],long int lb,long int ub)
- {
- long int m;
- if (lb < ub)
- {
- m = (lb+ub)/2;
- mergesort(a, lb, m);
- mergesort(a, m+1, ub);
- merge(a, lb, m, ub);
- }
- return;
- }
- long int partition(int a[], long int lb, long int ub)
- {
- long int down, up;
- int val, temp;
- val = a[lb];
- down = lb+1;
- up = ub;
- while(down<=up)
- {
- while (down<=up && a[down]<=val)
- down = down + 1;
- while (a[up]>val)
- up = up - 1;
- if (down < up)
- {
- temp = a[down];
- a[down] = a[up];
- a[up] = temp;
- }
- }
- a[lb] = a[up];
- a[up] = val;
- return up;
- }
- void quicksort(int a[],long int lb, long int ub)
- {
- long int p;
- if (lb<ub)
- {
- p = partition(a, lb, ub);
- quicksort(a, lb, p-1);
- quicksort(a, p+1, ub);
- }
- return;
- }
- void dataread(int a[])
- {
- FILE *fp;
- long int i;
- fp=fopen("data.txt","r");
- for(i=0;i<len;i++)
- {
- fscanf(fp,"%d",&a[i]);
- }
- fclose(fp);
- }
- int main(void)
- {
- int a[len],nextrand;
- long int i;
- double time_elapsed,time;
- clock_t t1,t2,t3,t4;
- FILE *fp;
- fp=fopen("data.txt","w");
- for(i=0;i<len;i++)
- {
- nextrand = rand()%100;
- fprintf(fp,"%d\n",nextrand);
- }
- fclose(fp);
- printf("\t\t Merge\t\t Quick\n");
- for(i=10;i<=len;i=i*10) //multiples of 10 number of integers starting from 10
- {
- printf("%ld integers",i);
- dataread(a);
- t1 = clock();
- mergesort(a,0,i);
- t2 = clock();
- time_elapsed = (double)(t2-t1)/CLOCKS_PER_SEC;
- printf("\t%lf\t",time_elapsed);
- quicksort(a,0,i);
- quicksort(a,0,i);
- t3 = clock();
- mergesort(a,0,i);
- t4 = clock();
- time = (double)(t4-t3)/CLOCKS_PER_SEC;
- printf("\t%lf",time);
- printf("\n");
- }
- return 0;
- }
- expt 3
- #include<stdio.h>
- #include<stdlib.h>
- #include<conio.h>
- void getminmax(int a[],int lb,int ub,int*fmin,int*fmax)
- {
- int m,hmin,hmax,gmin,gmax;
- if(ub==lb)
- {
- *fmin = *fmax = a[ub];
- return;
- }
- if(ub==lb+1)
- {
- if(a[ub]<=a[lb])
- {
- *fmin=a[ub];
- *fmax=a[lb];
- return;
- }
- else
- {
- *fmin=a[lb];
- *fmax=a[ub];
- return;
- }
- }
- m=(lb+ub)/2;
- getminmax(a,lb,m,&hmin,&hmax);
- getminmax(a,m+1,ub,&gmin,&gmax);
- if(hmin <= gmin)
- *fmin = hmin;
- else *fmin = gmin;
- if(hmax > gmax)
- *fmax = hmax;
- else *fmax = gmax;
- return;
- }
- void main(void)
- {
- int n,i,a[30000],nextrand,min,max;
- FILE *fp;
- min=0;
- max=0;
- printf("Enter number of integers: ");
- scanf("%d",&n);
- fp=fopen("data.txt","w");
- for(i=0;i<n;i++)
- {
- nextrand=rand()%100;
- fprintf(fp,"%d ",nextrand);
- }
- fclose(fp);
- fp=fopen("data.txt","r");
- for(i=0;i<n;i++)
- {
- fscanf(fp,"%d ",&a[i]);
- printf("%d ",a[i]);
- }
- fclose(fp);
- getminmax(a,0,n-1,&min,&max);
- printf("\n\nMaximum = %d",max);
- printf("\nMinimum = %d\n",min);
- getch();
- }
- expt 4
- #include<stdio.h>
- void shiftup(int a[][512],int n,int lb,int ub)
- {
- int i,j; //function to circular shift
- j=a[lb][n];
- for(i=lb;i<ub;i++)
- a[i][n]=a[i+1][n];
- a[ub][n]=j;
- }
- void shiftdown(int a[][512],int n,int lb,int ub)
- {
- int i,j; //function for reverse circular shift
- j=a[ub][n];
- for(i=ub;i>lb;i--)
- a[i][n]=a[i-1][n];
- a[lb][n]=j;
- }
- void compute(int a[][512],int lb,int ub)
- {
- int m,i,j,k=(ub-lb)/2,d;
- if(ub-lb==1)
- {
- a[ub][0]=lb+1; //only two teams
- a[lb][0]=ub+1;
- return;
- }
- m=(lb+ub)/2; // divide stage
- compute(a,lb,m);
- compute(a,m+1,ub);
- j=m+2;
- for(i=lb;i<=m;i++) //creating a new upper column after all dealing with all the sub parts.
- {
- a[i][k]=j;
- j++;
- }
- for(i=k+1;i<ub;i++) // circular shifting the columns
- {
- for(j=lb;j<=m;j++)
- a[j][i]=a[j][i-1];
- shiftup(a,i,lb,m);
- }
- j=lb+1;
- for(i=m+1;i<=ub;i++) //creating a new lower column after all dealing with all the sub parts.
- {
- a[i][k]=j;
- j++;
- }
- for(i=k+1;i<ub;i++) //reverse circular shifting the columns
- {
- for(j=m+1;j<=ub;j++)
- a[j][i]=a[j][i-1];
- shiftdown(a,i,m+1,ub);
- }
- }
- void main()
- {
- int i,j,n,a[512][512];
- printf("Enter the number of players: ");
- scanf("%d",&n);
- compute(a,0,n-1);
- printf("The tournament schedule is:\n\nDays:\t");
- for(i=1;i<n;i++)
- printf("D%.2d ",i); //displaying the days row
- printf("\n");
- printf("Players:\n");
- for(i=0;i<n;i++)
- {
- printf("%2d\t",i+1); //displaying team number
- for(j=0;j<n-1;j++)
- printf("%3d ",a[i][j]); //displaying the required schedule
- printf("\n");
- }
- }
- expt 5
- #include<stdio.h>
- #include<conio.h>
- typedef struct
- {
- float p[20],w[20];
- }knapsack;
- void bubblesort(knapsack *k, int n, float a[])
- {
- int i, j;
- float temp;
- for (i=0; i<n; i++)
- {
- a[i] = k->p[i]/k->w[i];
- }
- for (i=0; i<n-1; i++)
- for (j=0; j<n-i-1; j++)
- if (a[j] < a[j+1])
- {
- temp = a[j];
- a[j] = a[j+1];
- a[j+1] = temp;
- temp = k->p[j];
- k->p[j] = k->p[j+1];
- k->p[j+1] = temp;
- temp = k->w[j];
- k->w[j] = k->w[j+1];
- k->w[j+1] = temp;
- }
- return;
- }
- void fknap(knapsack k, int n, int M)
- {
- int i;
- float cp=0,cw=0,a[20];
- bubblesort(&k,n,a);
- printf("The sorted list is:\n");
- for (i=0; i<n; i++)
- {
- printf("\n%.0f | ",k.p[i]);
- printf("%.0f | ",k.w[i]);
- printf("%f ",a[i]);
- }
- printf("\n");
- for (i=0; i<n; i++)
- if ((cw+k.w[i]) < M)
- {
- cp = cp+k.p[i];
- cw = cw+k.w[i];
- }
- else
- {
- cp = cp+((k.p[i]/k.w[i])*(M-cw));
- cw = M;
- break;
- }
- printf("\nProfit = %f\n",cp);
- printf("Weight = %f\n",cw);
- return;
- }
- void knap0_1(knapsack k, int n, int M)
- {
- int i,cp=0,cw=0;
- float a[20];
- bubblesort(&k,n,a);
- printf("The sorted list is:\n");
- for (i=0; i<n; i++)
- {
- printf("\n%.0f | ",k.p[i]);
- printf("%.0f | ",k.w[i]);
- printf("%f ",a[i]);
- }
- printf("\n");
- for (i=0; i<n; i++)
- {
- if ((cw+k.w[i]) <= M)
- {
- cp = cp+k.p[i];
- cw = cw+k.w[i];
- }
- if (cw == M)
- break;
- }
- printf("\nProfit = %d\n",cp);
- printf("Weight = %d\n",cw);
- return;
- }
- void main(void)
- {
- int i,n,M,ch;
- knapsack k;
- printf("Enter no. of items: ");
- scanf("%d",&n);
- printf("Enter the profits of %d items: ",n);
- for (i=0; i<n; i++)
- scanf("%f", &k.p[i]);
- printf("Enter the weights of %d items: ",n);
- for (i=0; i<n; i++)
- scanf("%f", &k.w[i]);
- printf("Enter maximum capacity of the sack: ");
- scanf("%d",&M);
- do
- {
- printf("\nEnter choice from the following\n1. Fractional Knapsack\n2. 0/1 Knapsack\n3. Exit\n\n");
- scanf("%d",&ch);
- switch(ch)
- {
- case 1 : printf("Fractional Knapsack's result:\n");
- fknap(k,n,M);
- break;
- case 2 : printf("0/1 Knapsack's result:\n");
- knap0_1(k,n,M);
- break;
- case 3 : printf("THANK YOU\n");
- break;
- default : printf("INVALID CHOICE\n");
- break;
- }
- }while(ch>=1&&ch<=2);
- getch();
- }
- expt 6
- #include <stdio.h>
- #include <stdlib.h>
- #define INFY 32000
- void input_weight_matrix(int v[][50],int n,int e)
- {
- int x,y,cost;
- for(x=1;x<=n;x++)
- for(y=1;y<=n;y++)
- v[x][y]=INFY;
- while(n>0)
- v[n][n--]=0;
- while(e>0)
- {
- printf("Enter Edge as\"u_v_cost\":");
- scanf("%d %d %d",&x,&y,&cost);
- v[x][y]=cost;
- v[y][x]=cost;
- e--;
- }
- }
- void add_edge(int mcst[][50],int x,int y,int w)
- {
- mcst[x][y]=w;
- mcst[y][x]=w;
- }
- void add(int a[],int *n,int x)
- {
- a[(*n)]=x;
- (*n)++;
- }
- int extract(int a[],int *n,int b)
- {
- int r,i;
- for(i=0;a[i]!=b;i++);
- r=a[i];
- (*n)--;
- for(i;i<(*n);i++)
- a[i]=a[i+1];
- return r;
- }
- void primms_mcst(int w[][50],int mcst[][50],int n,int s)
- {
- int v[50],uv[50],vn=0,uvn=0,i=1,j=1,x,y,mw=INFY;
- add(v,&vn,s);
- while(i<=n)
- {
- if(i!=s)
- add(uv,&uvn,i);
- i++;
- }
- while(uvn>0)
- {
- mw=INFY;
- for(i=0;i<vn;i++)
- for(j=0;j<uvn;j++)
- {
- if((w[(v[i])][(uv[j])])<mw)
- {
- x=v[i];
- y=uv[j];
- mw=w[v[i]][uv[j]];
- }
- }
- add_edge(mcst,x,y,mw);
- v[vn++]=extract(uv,&uvn,y);
- }
- }
- void display_mat(int a[][50],int n)
- {
- int i,j;
- for(i=1;i<=n;i++)
- {
- printf("\n");
- for(j=1;j<=n;j++)
- if(a[i][j]==INFY)
- printf(" Inf");
- else printf("%4d",a[i][j]);
- }
- }
- void print_mcst(int mcst[][50],int n)
- {
- int cost=0,i,j;
- for(i=1;i<=n;i++)
- for(j=i;j<=n;j++)
- {
- if(mcst[i][j]==0)
- continue;
- printf("(%d,%d),",i,j);
- cost+=mcst[i][j];
- }
- printf("\nMinimum Cost = %d",cost);
- }
- int main()
- {
- int w[50][50],n,mcst[50][50],e,s;
- printf("Enter the No.of vertices and edges: ");
- scanf("%d %d",&n,&e);
- input_weight_matrix(w,n,e);
- display_mat(w,n);
- printf("\nEnter the starting node: ");
- scanf("%d",&s);
- primms_mcst(w,mcst,n,s);
- printf("\nPrims MCST_MAT:\n");
- display_mat(mcst,n);
- printf("\nThat is RESULT: ");
- print_mcst(mcst,n);
- return 0;
- }
- expt 7
- #include<stdio.h>
- void init(int COST[][50],int D[][50],int n)
- {
- int i,j,c;
- for (i=0; i<n; i++)
- for (j=0; j<n; j++)
- {
- COST[i][j] = 999;
- D[i][j] = -1;
- }
- c=n-1;
- while(c>=0)
- {
- COST[c][c--]=0;
- }
- }
- void readEdges(int COST[][50],int D[][50],int e)
- {
- int u,v,c;
- while (e!=0)
- {
- printf("Enter edge as \"u_v_cost\": ");
- scanf("%d %d %d",&u,&v,&c);
- COST[u-1][v-1]=c;
- D[u-1][v-1]=u;
- e--;
- }
- }
- void displayMat(int Mat[][50], int n)
- {
- int i,j;
- for (i=0;i<n;i++)
- {
- for (j=0;j<n;j++)
- printf("%3d ", Mat[i][j]);
- printf("\n");
- }
- }
- void apsp(int COST[][50],int A[][50],int D[][50],int n)
- {
- int i,j,k,t;
- for (i=0; i<n; i++)
- for (j=0;j<n;j++)
- A[i][j]=COST[i][j];
- for (k=0;k<n;k++)
- for (i=0;i<n;i++)
- for(j=0;j<n;j++)
- {
- t = A[i][k]+A[k][j];
- if (A[i][j]>t)
- {
- A[i][j] = t;
- D[i][j] = k+1;
- }
- }
- }
- void pathfinding(int COST[][50],int D[][50],int s, int d)
- {
- int i=1,j,FINAL[50];
- j=d;
- FINAL[0]=d;
- while(D[s-1][d-1]!= -1)
- {
- FINAL[i++]=D[s-1][d-1];
- if (COST[d-1][j-1]==999)
- {
- s = D[s-1][d-1];
- continue;
- }
- d = D[s-1][d-1];
- }
- printf("\nPath: ");
- for(j=i-1;j>0;j--)
- printf("%d-",FINAL[j]);
- printf("%d",FINAL[0]);
- }
- int main(void)
- {
- int A[50][50],COST[50][50],D[50][50],n,e,s,q;
- printf("Enter no. of vertices: ");
- scanf("%d",&n);
- printf("Enter no. of edges: ");
- scanf("%d",&e);
- init(COST,D,n);
- readEdges(COST,D,e);
- printf("\nWeight Mat:\n");
- displayMat(COST,n);
- printf("Decision Mat initially:\n");
- displayMat(D,n);
- apsp(COST,A,D,n);
- printf("\nFinal Length Mat:\n");
- displayMat(A,n);
- printf("Final Decision Mat:\n");
- displayMat(D,n);
- printf("\nEnter starting and ending nodes: ");
- scanf("%d%d",&s,&q);
- printf("Minimum Length between %d and %d = %d",s,q,A[s-1][q-1]);
- pathfinding(COST,D,s,q);
- return 0;
- }
- expt 8
- #include<stdio.h>
- typedef struct
- {
- int n[50];
- int v;
- int min;
- }PS;
- PS tsp(int s,PS list,int D[][50],int m)
- {
- int i,j;
- PS nlist,npath,nmin;
- if(list.v==0)
- {
- nmin.min=D[s][1];
- nmin.n[m-1]=s;
- nmin.v=m;
- return nmin;
- }
- for(i=0;i<list.v;i++)
- {
- nlist.v=0;
- for(j=0;j<list.v;j++)
- if(i!=j)
- nlist.n[nlist.v++]=list.n[j];
- npath=tsp(list.n[i],nlist,D,m);
- npath.min=D[s][list.n[i]]+npath.min;
- npath.n[m-list.v-1]=s;
- if(i==0)
- nmin=npath;
- else if(npath.min<nmin.min)
- nmin=npath;
- }
- return nmin;
- }
- void display(PS path)
- {
- int i;
- printf("\n\nThe minimum cost is: %d\n",path.min);
- printf("\n\nThe path is...\n");
- for(i=0;i<path.v;i++)
- printf("%d--",path.n[i]);
- printf("%d",path.n[0]);
- }
- int main()
- {
- int i,j,D[50][50],m;
- PS graph,path;
- printf("Enter the number of nodes: ");
- scanf("%d",&m);
- for(i=1;i<=m;i++)
- {
- for(j=1;j<=m;j++)
- if(i==j)
- D[j][j]=0;
- else
- {
- printf("Enter distance from node %d to %d: ",i,j);
- scanf("%d",&D[i][j]);
- }
- if(i>1)
- graph.n[i-2]=i;
- }
- graph.v=m-1;
- path=tsp(1,graph,D,m);
- display(path);
- return 0;
- }
- expt 9
- #include<stdio.h>
- #include<conio.h>
- #include<math.h>
- void display(int x[],int n)
- {
- int i,j;
- for (i=0; i<n; i++)
- {
- for (j=0; j<n; j++)
- if(x[i]==j)
- printf("Q ");
- else printf("# ");
- printf("\n");
- }
- printf("\n\n");
- }
- void nqueens(int x[],int r,int n)
- {
- int c;
- for(c=0;c<n; c++)
- {
- if(place(x,r,c)==1)
- {
- x[r]=c;
- if(r==n-1)
- display(x,n);
- else nqueens(x,r+1,n);
- }
- }
- }
- int place(int x[],int r,int c)
- {
- int j;
- for(j=0; j<r; j++)
- if(x[j]==c || abs(x[j]-c)==abs(j-r))
- return 0;
- return 1;
- }
- int main()
- {
- int x[20],n;
- printf("Enter no of queens: ");
- scanf("%d",&n);
- nqueens(x,0,n);
- getch();
- return 0;
- }
- expt 10
- #include<stdio.h>
- #include<conio.h>
- void display(int x[], int n)
- {
- int i;
- for (i=0; i<n; i++)
- printf("%d ",x[i]);
- printf("\n");
- }
- void sumofsub(int w[],int x[],int M,int n,int s,int k,int r)
- {
- int i;
- for (i=k; i<n; i++)
- x[i]=0;
- x[k]=1;
- if(s+w[k]==M)
- display(x,n);
- else if(s+w[k]+w[k+1]<=M)
- sumofsub(w,x,M,n,s+w[k],k+1,r-w[k]);
- if(s+r-w[k]>=M && s+w[k+1]<=M)
- {
- x[k]=0;
- sumofsub(w,x,M,n,s,k+1,r-w[k]);
- }
- }
- int main()
- {
- int i,r=0;
- int w[20],n,M,x[20];
- printf("Enter no of weights: ");
- scanf("%d",&n);
- printf ("Enter the weights: ");
- for(i=0; i<n; i++)
- {
- scanf("%d",&w[i]);
- r=r+w[i];
- }
- printf("Enter required sum: ");
- scanf("%d",&M);
- printf("Selected List is:\n");
- sumofsub(w,x,M,n,0,0,r);
- return 0;
- }
- graph color
- #include<conio.h>
- #include<stdio.h>
- #include<math.h>
- int n,m,x[20]={0},ct=0,adj[10][10];
- void nextval(int k)
- {
- int j=1;
- x[k]=(x[k]+1)%(m+1);
- if(x[k]==0)
- return;
- while(j<k)
- {
- if(adj[j][k]==1 && x[j]==x[k])
- {
- x[k]=(x[k]+1)%(m+1);
- if(x[k]==0)
- return;
- j=1;
- }
- else j++;
- }
- return;
- }
- void dis()
- {
- int i;
- ct=ct+1;
- printf("soluition=%d\n",ct);
- for(i=1;i<=n;i++)
- printf("%d ",x[i]);
- printf("\n");
- }
- void colorg(int k)
- {
- int i;
- for(i=1;i<=n;i++)
- {
- nextval(k);
- if(x[k]==0)
- return;
- if(k==n)
- {
- dis();
- }
- else colorg(k+1);
- }
- }
- void main()
- {
- int i,j;
- clrscr();
- printf("Enter no of nodes\n");
- scanf("%d",&n);
- printf("Enter no of colors\n");
- scanf("%d",&m);
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- scanf("%d",&adj[i][j]);
- colorg(1);
- getch();
- }
- lcs and clcs
- #include<stdio.h>
- #include<string.h>
- int i,j,m,n,a,L[20][20];
- char x[15],y[15],D[20][20];
- void print_lcs(int i,int j)
- {
- if(i==0 || j==0)
- return;
- if(D[i][j]=='d')
- {
- print_lcs(i-1,j-1);
- printf(" %c",x[i-1]);
- }
- else if(D[i][j]=='u')
- print_lcs(i-1,j);
- else
- print_lcs(i,j-1);
- }
- void lcs(void)
- {
- m=strlen(x);
- n=strlen(y);
- for(i=0; i<=m; i++)
- L[i][0]=0;
- printf("\n\n");
- for(i=0; i<=n; i++)
- {
- printf("0 \t");
- L[0][i]=0;
- }
- printf("\n");
- for(i=1; i<=m ;i++)
- {
- printf("0 \t");
- for(j=1; j<=n; j++)
- {
- if(x[i-1]==y[j-1])
- {
- L[i][j]=L[i-1][j-1]+1;
- D[i][j]='d';
- printf("%d D\t",L[i][j]);
- }
- else if(L[i-1][j] > L[i][j-1])
- {
- L[i][j] = L[i-1][j];
- D[i][j] = 'u';
- printf("%d U\t",L[i][j]);
- }
- else
- {
- L[i][j]=L[i][j-1];
- D[i][j]='l';
- printf("%d L\t",L[i][j]);
- }
- }
- printf("\n");
- }
- printf("\nLongest common subsequence is :");
- print_lcs(m,n);
- printf("\n");
- printf("The length of Subsequence is: %d",L[m][n]);
- }
- void main()
- {
- printf("Enter 1st sequence : ");
- scanf("%s",x);
- printf("Enter 2nd sequence : ");
- scanf("%s",y);
- lcs();
- printf("\n");
- getch();
- }
- naive pattern
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- int brute_force(char x[],char y[])
- {
- int i,j,n,m;
- n = strlen(x);
- m = strlen(y);
- for (i=0; i<n-m; i++)
- {
- j = 0;
- while(j<m && x[i+j]==y[j])
- j = j+1;
- if (j==m)
- return i; //starting index of the text part where pattern is matched
- }
- return -1; //pattern not matched in the entire text
- }
- int main()
- {
- char t[20],p[10];
- int result;
- printf("Enter the text: ");
- scanf("%s",t);
- printf("Enter the pattern needed to be found: ");
- scanf("%s",p);
- result = brute_force(t,p);
- if(result != -1)
- printf("\nThe pattern is matched in the text from: %d index of the text.",result);
- else printf("\nThe pattern didn't matched!!!");
- printf("\n");
- getch();
- }
- kmp and cmkp
- #include<conio.h>
- #include<stdio.h>
- #include<string.h>
- int f[30];
- void kmpfail(char p[],int m)
- {
- int i=1,j=0;
- f[0]=0;
- while(i<m)
- {
- if(p[j]==p[i])
- {
- f[i]=j+1;
- i=i+1,j=j+1;
- }
- else if(j>0)
- j=f[j-1];
- else
- {
- f[i]=0;
- i=i+1;
- }
- }
- return;
- }
- int kmp(char t[],char p[], int n,int m)
- {
- int i=0,j=0;
- while(i<n)
- {
- if(p[j]==t[i])
- if(j==m-1)
- return i-m+1;
- else i=i+1,j=j+1;
- else if(j>0)
- j=f[j-1];
- else i=i+1;
- }
- return -1;
- }
- void main()
- {
- int n,m;
- char t[30],p[10];
- clrscr();
- printf("Enter text\n");
- gets(t);
- n=strlen(t);
- printf("Enter pattern\n");
- gets(p);
- m=strlen(p);
- kmpfail(p,m);
- if(kmp(t,p,n,m)!=-1)
- printf("pattern is present at %d",kmp(t,p,n,m));
- else printf("pattern not found");
- getch();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement