Mohammad Erfan Hossain's Blog

/* UVA id: shoaib05 Accepted Time; 1.236  */ #include<iostream> #include<string> #include<algorithm> #include<string.h> #include<cstdio> using namespace std; int main() { freopen("in.txt","r",stdin); int len,z,i,j,ln,x; string temp,temp2,temp3,s; char ch[300]; bool flag; size_t found; while(cin>>s) { len=s.size(); ln=3; flag=false; temp3="#"; x=0; while(ln<len) { z=len-ln; for(i=x;i<=z;i++) { temp=s.substr(i,ln); strcpy(ch,temp.c_str()); reverse(ch,ch+ln); temp2=ch; if(temp==temp2) { if(temp3[0]=='#') { temp3=temp; x=i+1; continue; } else if(temp==temp3) continue; else if(temp.size()>temp3.size()) { found=temp.find(temp3); if(found>temp.size()) { flag=true; cout<<s<<endl; break; } ...

/* Solved by using Edit_Distance Algorithm */ /* uva id: shoaib05 Accepted  Time: 0.006 */ #include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> using namespace std; int table[1010][1010]; int main() { int test,t,i,j,len; char x[1010],y[1010]; scanf("%d",&test); t=1; while(t<=test) { scanf("%s",x); len=strlen(x); strcpy(y,x); reverse(y,y+len); for(i=0;i<=len;i++) table[i][0]=i; for(j=0;j<=len;j++) table[0][j]=j; for(i=1;i<=len;i++) { for(j=1;j<=len;j++) { if(x[i-1]==y[j-1]) table[i][j]=table[i-1][j-1]; else table[i][j]=min(table[i-1][j-1],min(table[i-1][j],table[i][j-1]))+1; } } printf("Case %d: %d\n",t++,table[len][len]/2); } return 0; }

/* Solved by using Edit-Distance Algorithm */ /* uva id- shoaib05 Accpted Time: 0.001 */ #include<stdio.h> #include<algorithm> #include<iostream> using namespace std; char x[5010],y[5010]; int len1,len2,table[5010][5010]; void buildTable() { int i,j; for(i=0;i<=len1;i++) table[i][0]=i; for(j=0;j<=len2;j++) table[0][j]=j; for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(x[i-1]==y[j-1]) table[i][j]=table[i-1][j-1]; else table[i][j]=min(table[i-1][j-1],min(table[i-1][j],table[i][j-1]))+1; } } } int main() { while(scanf("%d %s %d %s",&len1,x,&len2,y)==4) { buildTable(); printf("%d\n",table[len1][len2]); } return 0; }

/* Solved by using Edit-Distance Algorithm */ /* UVA id: shoaib05 Accepted Time: 0.103 */ #include<iostream> #include<string.h> #include<algorithm> #include<cstdio> using namespace std; char x[90],y[90]; int len1,len2,table[90][90]; void buildTable() { int i,j; for(i=0;i<=len1;i++) table[i][0]=i; for(j=0;j<=len2;j++) table[0][j]=j; for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(x[i-1]==y[j-1]) table[i][j]=table[i-1][j-1]; else table[i][j]=min(table[i-1][j-1],min(table[i-1][j],table[i][j-1]))+1; } } } void result() { int i=len1,j=len2; int cnt=1; cout<<table[i][j]<<endl; while(i || j) { if(i>0 && y>0 &&(x[i-1]==y[j-1])) { i--; j--; continue; } if(i>0 && (table[i-1][j]+1==table[i][j])) { cout<<cnt++<<" Delete "<<i<<endl; i--; } else if(i>0 && j...

/*  Using Edit_Distance Algorithm */ #include<iostream> #include<algorithm> #include<string> using namespace std; string s1,s2; int len1,len2,table[22][22]; void buildTable() { int i,j; for(i=0;i<=len1;i++) table[i][0]=i; for(j=0;j<=len2;j++) table[0][j]=j; for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1]) table[i][j]=table[i-1][j-1]; else table[i][j]=min(table[i-1][j-1],min(table[i-1][j],table[i][j-1]))+1; } } } void result() { int i=len1,j=len2; while(i || j) { if(s1[i-1]==s2[j-1]) { i--; j--; continue; } if(j>0 && (table[i][j]==table[i][j-1]+1)) { cout<<"I"<<s2[j-1]; if(i<=8) cout<<"0"; cout<<i+1; j--; } else if(i>0 && j>0 && (table[i][j]==table[i-1][j-1]+1)) { cout<<"C"<<s2[j-1]; if(i<=9) cout<<"0"; cout<<i; i--; j-...

/* Solution of uva-11512 using map and Trie */ #include<iostream> #include<map> #include<string> #include<string.h> using namespace std; int trie[501500][4]; char newarr[1005],ch[1005]; int idx,ll; bool createTrie(string s) { strcpy(ch,s.c_str()); int ci=0,li=0,i,j,k; k=0; ll=0; bool flag=false; for(i=0;ch[i];i++) { switch(ch[i]) { case 'A': j=0; break; case 'C': j=1; break; case 'G': j=2; break; case 'T': j=3;break; } if(trie[ci][j]==0) { idx++; trie[ci][j]=idx; ci=idx; } else { ci=trie[ci][j]; newarr[k]=ch[i]; k++; newarr[k]='\0'; flag=true; ll++; } } return flag; } int main() { int test,i,j,len,y,l,val,vl; string str,input,output; cin>>test; map<string,int> mymap; map<string,int>::iterator it,it2; bool flag; while(test--) { cin>>str; len=str....

/* structure  of map: ------------------------------------------------------------------- |      int             |   string        |      int                        | |Length of string| input string  |  Repeted number  | ------------------------------------------------------------------- Input: ab abcdef ab d ab ab ab Then, map's structure: ------------------------------------- | 1   |      d        |          1      | | 2   |     ab       |          5      | | 6   |   abcdef   |         1      | ------------------------------------- */ #include<iostream> #include<map> #include <string...

/* String permutation according the permuted string size  using C++ STL* and display  lexicographic order , using next_permutation function*/ #include<iostream> #include <set> #include<map> #include <string> #include<string.h> #include<algorithm> #define MAX_SIZE 100 using namespace std; int main () { string str,temp; map<int,set<string>> mymap; char ch[MAX_SIZE]; int i,j,len,length; cin>>str; len=str.size(); strcpy(ch,str.c_str()); sort(ch,ch+len); str=ch; for(i=0;i<len;i++) { for(j=1;j<=len-i;j++) { temp=str.substr(i,j); strcpy(ch,temp.c_str()); length=temp.size(); do { mymap[length].insert(ch); }while(next_permutation(ch,ch+j)); } } map<int,set<string>>::iterator mit; set<string>::iterator sit; for(mit=mymap.begin();mit!=mymap.end();mit++) for(sit=mit->second.begin();sit!=mit->second.end();sit++) cou...

/* String Permutation Using STL C++ and Print Lexicographic order     using next_permutation function. */ #include<iostream> #include <set> #include <string> #include<string.h> #include<algorithm> #define MAX_SIZE 100 using namespace std; int main () {     string str,temp;     set<string> myset;     char ch[MAX_SIZE];     int i,j,len;     cin>>str;     len=str.size();     strcpy(ch,str.c_str());     sort(ch,ch+len);     str=ch;     for(i=0;i<len;i++)     {         for(j=1;j<=len-i;j++)         {             temp=str.substr(i,j);             strcpy(ch,temp.c_str());      ...