There are several algorithm to solve pattern search from a provided string problem. To solve such problem using Naive method(for all the char of the provided string check whether the pattern contains or not ). It takes O(m*n),here m = string length of pattern and n= string length of the text. There are several algorithm to solve
Category: Tutorial
Longest Increasing Subsequence
LIS problem has a recursive solution and this also can be solved using DP. Recursive solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <cstdlib> using namespace std; int lis(int arr[],int length,int *max_length) { if(length==1) return 1; int res,max_end_here=1; //recursively we get all LIS those are ending with arr[0],arr[1] //...and arr[length-1] and if max ending with arr[length-1] //requires to be upadted then do it. for(int i=1;i<length;i++) { res = lis(arr,i,max_length); if(arr[i-1]<arr[length-1] && res+1>max_end_here) max_end_here = res+1; } if(max_end_here>*max_length) *max_length = max_end_here; return max_end_here; } int main() { int sz,max_length; int *arr; cout<<"Enter size:\n"; cin>>sz; cout<<"Enter elements:\n"; arr = (int*)malloc(sizeof(int)*sz); for(int i=0;i<sz;i++) { cin>>arr[i]; } max_length = 1; lis(arr,sz,&max_length); cout<<"LIS size = "<<max_length<<"\n"; free(arr); return 0; } |
But the solution has overlapping substructure property The same solution is calculated more than once)it can be solved using DP. DP Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <cstdlib> #include <cstring> using namespace std; int DPLIS(int arr[],int length) { int *LIS_ANS; LIS_ANS = (int*)malloc(sizeof(int)*length); //memset(LIS_ANS,1,sizeof(LIS_ANS)); for(int i=0;i<length;i++) LIS_ANS[i]=1; for(int i=1;i<length;i++) { for(int j=0;j<i;j++) { if( arr[i]>arr[j] && LIS_ANS[i] < LIS_ANS[j]+1 ) LIS_ANS[i] = LIS_ANS[j]+1; } } int mx = 2; for(int i=0;i<length;i++) if(mx<LIS_ANS[i]) mx = LIS_ANS[i]; free(LIS_ANS); return mx; } int main() { int sz; int *arr; cout<<"Enter size:\n"; cin>>sz; cout<<"Enter elements:\n"; arr = (int*)malloc(sizeof(int)*sz); for(int i=0;i<sz;i++) { cin>>arr[i]; } cout<<"LIS size = "<<DPLIS(arr,sz)<<"\n"; free(arr); return 0; } |
Time complexity of this solution is O(N*N). Better Solution with Time Complexity O(N*logN): Lets assume
Miscellaneous
Learning Sites: To learn Click Here Some Problems About Linked List Dynamic Memory Allocation: Code Snippet:
|
1 2 3 4 5 6 7 8 |
int dim; cin>>dim; string **s = new string *[dim]; s[0] = new string[100]; s[1] = new string[100]; s[0][1]="ajksdhjkasdh"; s[1][0]="sswd"; cout<<s[1][0]<<" "<<s[0][1]<<"\n"; |
BellmanFord Algorithm: Take all the edge in a struct as:
|
1 |
Struct Edge{int source,destination,cost}; |
Relax all the edge for (node-1)(e.g. total number of node of the vertex) number of time. After that check one more time if all the edges are