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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
|
private ArrayList WagnerAndFisher(ref String[] tabMots, String mot)
{
int tailleTab = tabMots.Length;
int longMot = mot.Length;
int[] longueur = new int[tailleTab];
String temp;
Boolean modif = false;
do
{
modif = false;
for (int i = 1; i < tabMots.Length; i++)
{
if (tabMots[i].Length > tabMots[i - 1].Length)
{
modif = true;
temp = tabMots[i];
tabMots[i] = tabMots[i - 1];
tabMots[i - 1] = temp;
}
}
}while (modif);
for (int cptMots = 0; cptMots < tailleTab; cptMots++)
{
int longMotTest = tabMots[cptMots].Length;
char[] tab_char = new char[longMotTest];
tab_char = tabMots[cptMots].ToUpper().ToCharArray();
int[,] matrice = new int[longMotTest, longMot];
matrice[0, 0] = 0;
int m1;
int m2;
int m3;
for (int i = 1; i < longMotTest; i++)
{
matrice[i, 0] = matrice[i - 1, 0] + 1;
}
for (int j = 1; j < longMot; j++)
{
matrice[0, j] = matrice[0, j - 1] + 1;
}
for (int i = 1; i < longMotTest; i++)
{
for (int j = 1; j < longMot; j++)
{
if (tab_char[i] == mot[j])
{
m1 = matrice[i - 1, j - 1];
}
else
{
m1 = matrice[i - 1, j - 1] + 1;
}
m2 = matrice[i - 1, j] + 1;
m3 = matrice[i, j - 1] + 1;
if ((m1 <= m2) && (m1 <= m3))
{
matrice[i, j] = m1;
}
else if ((m2 <= m1) && (m2 <= m3))
{
matrice[i, j] = m2;
}
else if ((m3 <= m2) && (m3 <= m1))
{
matrice[i, j] = m3;
}
}
}
longueur[cptMots] = matrice[longMotTest - 1, longMot - 1] + cptMots;
}
int min = longueur[0];
String[] resultat = new String[tailleTab];
int cpt = 0;
for (int i = 0; i < tailleTab; i++)
{
if (min > longueur[i])
{
min = longueur[i];
resultat[0] = tabMots[i];
cpt = 1;
}
else if (min == longueur[i])
{
resultat[cpt] = tabMots[i];
cpt = cpt + 1;
}
}
ArrayList listeRetour = new ArrayList();
for (int i = 0; i < resultat.Length; i++)
{
listeRetour.Add(resultat[i]);
}
listeRetour.Sort();
return listeRetour;
} |
Partager