fork(5) download
copy 
  1. #include<bits/stdc++.h>
  2. //#define mx             100010
  3. //#define mod            1000000007
  4. //#define pi             2*acos(0.0)
  5. //#define ll             long long int
  6. //#define pp             pair<int,int>
  7. //#define ull            unsigned long long int
  8. //#define valid(tx,ty)   tx>=0&&tx<r&&ty>=0&&ty<c
  9. #define mem(arr,val)   memset(arr,val,sizeof(arr))
  10. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
  11. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
  12. //int biton(int p,int pos){return p=p|(1<<pos);}
  13. //int bitoff(int p,int pos){return p=p&~(1<<pos);}
  14. //bool bitcheck(int p,int pos){return (bool)(p&(1<<pos));}
  15. //ll POW(ll b,ll p) {ll Ans=1; while(p){if(p&1)Ans=(Ans*b);b=(b*b);p>>=1;}return Ans;}
  16. //ll BigMod(ll b,ll p,ll Mod) {ll Ans=1; while(p){if(p&1)Ans=(Ans*b)%Mod;b=(b*b)%Mod;p>>=1;}return Ans;}
  17. //ll ModInverse(ll p,ll Mod) {return BigMod(p,Mod-2,Mod);}
  18. using namespace std;
  19. int dp[101][101];
  20. string str1,str2;
  21. void print_path(){
  22.     int i=str1.length();
  23.     int j=str2.length();
  24.     while(i>0||j>0){
  25.         if(str1[i-1]==str2[j-1]){
  26.             i--;
  27.             j--;
  28.         }
  29.         else if(j>0&&dp[i][j]==dp[i][j-1]+1){
  30.             cout<<"I"<<str2[j-1];
  31.             if(i<=8) cout<<"0";
  32.             cout<<i+1;
  33.             j--;
  34.         }
  35.         else if(i>0&&j>0&&dp[i][j]==dp[i-1][j-1]+1){
  36.             cout<<"C"<<str2[j-1];
  37.             if(i<=9) cout<<"0";
  38.             cout<<i;
  39.             i--;
  40.             j--;
  41.         }
  42.  
  43.         else if(i>0&&dp[i][j]==dp[i-1][j]+1){
  44.             cout<<"D"<<str1[i-1];
  45.             if(i<=9) cout<<"0";
  46.             cout<<i;
  47.             i--;
  48.         }
  49.     }
  50.     cout<<"E\n";
  51. }
  52. int main(){
  53. //    freopen("Input.txt","r",stdin); freopen("Output.txt","w",stdout);
  54. //    ios_base::sync_with_stdio(false); cin.tie(NULL);
  55.     while(cin>>str1){
  56.         if(str1[0]=='#') break;
  57.         cin>>str2;
  58.         mem(dp,0);
  59.         for(int i=0;i<=str1.length();i++){
  60.             for(int j=0;j<=str2.length();j++){
  61.                 if(i==0){
  62.                     dp[i][j]=j;
  63.                 }
  64.                 else if(j==0){
  65.                     dp[i][j]=i;
  66.                 }
  67.                 else if(str1[i-1]==str2[j-1]){
  68.                     dp[i][j]=dp[i-1][j-1];
  69.                 }
  70.                 else{
  71.                     dp[i][j]=1+min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]));
  72.                 }
  73.             }
  74.         }
  75.         print_path();
  76.     }
  77.     return 0;
  78. }
  79. /**
  80. Sample Input
  81. abcde bcgfe
  82. #
  83. Sample Output
  84. Da01Cg03If04E
  85. **/
  86.  
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/h2k7z3
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!