#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

#define MIN(a,b,c) min(min(a,b),c)
#define MAX 100

using namespace std;

//string str1 = "ocurrance";
//string str2 = "occurrence";

//string str1 = "oi";
//string str2 = "occurrence";

string str1 = "mean";
string str2 = "name";

int len1 = str1.length();
int len2 = str2.length();
int delta = 2;

int MEMO[MAX][MAX];


void printMat(int M[][MAX]){
	for (int i = len1; i>=0 ; --i) {
		for (int j = 0; j <=len2; ++j) {
			printf("%d ", M[i][j]);
		}
		printf("\n");
	}
}

/*
    se ambos forem vogais ou consoantes, alpha = 1
    caso contrario, alpha = 3
*/
int alpha(int i, int j){
	char cx = str1[i-1];
	char cy = str2[j-1];

	if(cx == cy)
		return 0;

	if ( (cx=='a' || cx=='e' || cx=='i' || cx=='o' || cx=='u') &&  
         (cy=='a' || cy=='e' || cy=='i' || cy=='o' || cy=='u') )
     return 1;
    if ( !(cx=='a' || cx=='e' || cx=='i' || cx=='o' || cx=='u') &&  
         !(cy=='a' || cy=='e' || cy=='i' || cy=='o' || cy=='u') )
     return 1;

    return 3;

}

int ed(int i, int j){
	if (i == 0)
		return j*delta;

	if (j == 0)
		return i*delta;

	return MIN(alpha(i,j)+ed(i-1,j-1), delta+ed(i-1,j), delta+ed(i,j-1));
}

int edRECPD(int i, int j){
	if (i == 0){
		MEMO[0][j] = j*delta;
		return MEMO[0][j];
	}

	if (j == 0){
		MEMO[i][0] = i*delta;
		return MEMO[i][0];
	}

	if (MEMO[i][j] != -1)
		return MEMO[i][j];

	MEMO[i][j] =  MIN(alpha(i,j)+edRECPD(i-1,j-1), delta+edRECPD(i-1,j), delta+edRECPD(i,j-1));

	return MEMO[i][j];
}

int edPD(){
	for (int j = 0; j <=len2; ++j)
		MEMO[0][j] = j*delta;

	for (int i = 0; i <=len1; ++i)
		MEMO[i][0] = i*delta;

	for (int i = 1; i <=len1; ++i)
		for (int j = 1; j <=len2; ++j)
			MEMO[i][j] =  MIN(alpha(i,j)+MEMO[i-1][j-1], delta+MEMO[i-1][j], delta+MEMO[i][j-1]);

	return MEMO[len1][len2];
}



int main(int argc, char const *argv[])
{
	printf("Valor do Alinhamento Otimo M  = %d \n", ed(len1,len2));

	memset (MEMO, -1, sizeof MEMO);
	printf("REC PD: Valor do Alinhamento Otimo M = %d \n", edRECPD(len1,len2));
	printMat(MEMO);

	printf("PD: Valor do Alinhamento Otimo M = %d \n", edPD());
	printMat(MEMO);

	return 0;
}