151. Inverser les mots dans une chaîne

L’idée est d’abord de nettoyer les espaces superflus, puis d’inverser toute la chaîne et enfin d’inverser chaque mot individuellement.

public class InversionMots {
    public String inverserMots(String phrase) {
        char[] tab = phrase.toCharArray();
        int lent = 0;

        // Nettoyage des espaces en excès
        for (int rapide = 0; rapide < tab.length; rapide++) {
            if (tab[rapide] != ' ') {
                if (lent != 0) {
                    tab[lent++] = ' ';
                }
                int debut = rapide;
                while (debut < tab.length && tab[debut] != ' ') {
                    tab[lent++] = tab[debut++];
                }
                rapide = debut - 1;
            }
        }

        int taille = lent;
        inverser(tab, 0, taille - 1);

        // Inversion de chaque mot
        int i = 0;
        while (i < taille) {
            int j = i;
            while (j < taille && tab[j] != ' ') {
                j++;
            }
            inverser(tab, i, j - 1);
            i = j + 1;
        }

        return new String(tab, 0, taille);
    }

    private void inverser(char[] tab, int gauche, int droite) {
        while (gauche < droite) {
            char tmp = tab[gauche];
            tab[gauche] = tab[droite];
            tab[droite] = tmp;
            gauche++;
            droite--;
        }
    }
}

55. Rotation à droitte d'une chaîne

Une rotation à droite de k positions revient à placer les k derniers caractères au début de la chaîne. On obtient le résultat directement avec des sous-chaînes.

import java.util.Scanner;

public class RotationDroite {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.nextLine());
        String texte = sc.nextLine();
        int n = texte.length();
        k %= n;
        String resultat = texte.substring(n - k) + texte.substring(0, n - k);
        System.out.println(resultat);
    }
}

28. Recherche d'un motif avec KMP

L’algorithme de Knuth-Morris-Pratt consrtuit un tableau de bordures lps (longest prefix suffix) pour éviter les comparaisons inutiles.

public class RechercheKMP {
    public int strStr(String texte, String motif) {
        if (motif.isEmpty()) {
            return 0;
        }
        int m = motif.length();
        int n = texte.length();
        int[] lps = construireLps(motif);

        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && texte.charAt(i) != motif.charAt(j)) {
                j = lps[j - 1];
            }
            if (texte.charAt(i) == motif.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    private int[] construireLps(String motif) {
        int m = motif.length();
        int[] lps = new int[m];
        for (int i = 1, longueur = 0; i < m; i++) {
            while (longueur > 0 && motif.charAt(i) != motif.charAt(longueur)) {
                longueur = lps[longueur - 1];
            }
            if (motif.charAt(i) == motif.charAt(longueur)) {
                longueur++;
            }
            lps[i] = longueur;
        }
        return lps;
    }
}

459. Motif répété dans une chaîne

Méthode par concaténation

Si une chaîne est composée de répétitions d’un motif, la chaîne s + s contiendra s entre les deux occurrences, sauf aux extrémités.

public boolean motifRepete(String s) {
    int n = s.length();
    String doublee = s + s;
    String centre = doublee.substring(1, 2 * n - 1);
    return centre.contains(s);
}

Méthode par KMP

Le tableau lps de la chaîne donne la plus grande bordure. Si cette bordure découpe la chaîne en périodes entières, la chaîne est répétitive.

public boolean motifRepeteKMP(String s) {
    int n = s.length();
    if (n == 0) {
        return false;
    }
    int[] lps = new int[n];
    for (int i = 1, longueur = 0; i < n; i++) {
        while (longueur > 0 && s.charAt(i) != s.charAt(longueur)) {
            longueur = lps[longueur - 1];
        }
        if (s.charAt(i) == s.charAt(longueur)) {
            longueur++;
        }
        lps[i] = longueur;
    }
    int bordure = lps[n - 1];
    int periode = n - bordure;
    return bordure > 0 && n % periode == 0;
}