OJ Board

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
using namespace std;

typedef long long int L;
typedef unsigned long long int U;

int arr[85][85];
char op[85][85];
stack < pair<int,char> >st;
main()
{
      char str1[85], str2[85];
      int first = 1;
      while(gets(str1))
      {
            gets(str2);
            for(int i = 0;i<=strlen(str1);i++)
            {
                  arr[0][i] = i;
                  op[0][i] = 'd';
            }
            for(int i = 0;i<=strlen(str2);i++)
            {
                  arr[i][0] = i;
                  op[i][0] = 'i';
            }
            for(int i = 1;i<=strlen(str2);i++)
            {
                  for(int j = 1;j<=strlen(str1);j++)
                  {
                        arr[i][j] = arr[i-1][j]+1;
                        op[i][j] = 'i';
                        if(arr[i][j-1]+1 < arr[i][j])
                        {
                              arr[i][j] = arr[i][j-1]+1;
                              op[i][j] = 'd';
                        }
                        if(arr[i-1][j-1] + (str2[i-1]!=str1[j-1]) < arr[i][j])
                        {
                              arr[i][j] = arr[i-1][j-1] + (str2[i-1]!=str1[j-1]);
                              op[i][j] = 'r';
                        }
                        //cout<<arr[i][j]<<op[i][j]<<" ";
                  }
                  //cout<<endl;
            }
            if(first)
            	first = 0;
            else
            	printf("\n");
            int x = strlen(str2);
            int y = strlen(str1);
            cout<<arr[x][y]<<endl;;
            int c = 1;
            while(arr[x][y])
            {
                  int val = arr[x][y];
                  char oper = op[x][y];
                  if(op[x][y] == 'r')
                  {
                        x--;
                        y--;
                  }
                  else if(op[x][y] == 'i')
                        x--;
                  else
                        y--;
                  if(val > arr[x][y])
                  {
                        if(oper == 'i')
                        	  printf("%d Insert %d,%c\n",c++,min(x+2,y+1),str2[x]);
            			else if(oper == 'd')
                              printf("%d Delete %d\n", c++, y+1);
                        else
                              printf("%d Replace %d,%c\n",c++,y+1, str2[x]);
                  }
            }
      }
}

Code: Select all

iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx

Code: Select all

vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphuthdqcpkhdnuvlgslx

Code: Select all

iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx

Code: Select all

57
1 Replace 58,x
2 Replace 57,l
3 Replace 56,s
4 Replace 55,g
5 Replace 54,l
6 Replace 53,v
7 Replace 52,u
8 Replace 51,n
9 Replace 50,d
10 Replace 48,k
11 Replace 47,p
12 Replace 46,c
13 Replace 45,q
14 Replace 44,d
15 Replace 43,h
16 Replace 42,t
17 Replace 41,o
18 Replace 40,h
19 Replace 39,p
20 Replace 38,w
21 Replace 37,g
22 Replace 36,u
23 Replace 35,f
24 Replace 34,r
25 Replace 33,h
26 Replace 32,c
27 Replace 31,z
28 Replace 30,d
29 Replace 29,v
30 Replace 28,b
31 Replace 27,q
32 Replace 26,y
33 Replace 25,v
34 Replace 24,m
35 Replace 23,w
36 Replace 22,s
37 Replace 20,b
38 Replace 19,m
39 Replace 18,d
40 Replace 17,t
41 Replace 16,m
42 Replace 15,t
43 Replace 14,v
44 Replace 13,n
45 Replace 12,a
46 Replace 11,b
47 Replace 10,s
48 Replace 9,b
49 Replace 8,v
50 Replace 7,r
51 Replace 6,m
52 Replace 5,l
53 Replace 4,d
54 Replace 3,s
55 Replace 2,d
56 Replace 1,f
57 Insert 1,v

Code: Select all

vfdsdlmrvbsbanvtmtdmblswmvyqbvdzcrfubwphuhdqcpkhdnuvlasgulx