Concaténation de deux chaînes de caractères sans intersection

Question

J'ai besoin de concaténer deux chaînes de caractères dans une autre sans leur intersection (en termes de derniers/premiers mots).

En exemple :

"Some little d" + "les petits chiens sont si jolis" = "Certains petits chiens sont si jolis"

"Je t'aime" + "amour" = "Je t'aime".

Quel est le moyen le plus efficace de faire cela en Java ?

Answer 1

C'est parti - si la première ne contient même pas la première lettre de la deuxième chaîne, renvoyez simplement la concaténation. Sinon, on va du plus long au plus court sur la deuxième chaîne, en regardant si la première se termine par elle. Si c'est le cas, retournez les parties qui ne se chevauchent pas, sinon essayez une lettre plus courte.

 public static String docat(String f, String s) {
   if (!f.contains(s.substring(0,1)))
     return f + s;
   int idx = s.length();
   try {
     while (!f.endsWith(s.substring(0, idx--))) ;
   } catch (Exception e) { }
   return f + s.substring(idx + 1);
 }

 docat("Some little d", "little dogs are so pretty");
 -> "Some little dogs are so pretty"
 docat("Hello World", "World")
 -> "Hello World"
 docat("Hello", "World")
 -> "HelloWorld"

EDIT : En réponse au commentaire, voici une méthode utilisant des tableaux. Je ne sais pas comment tester ces méthodes correctement, mais aucune d'entre elles n'a pris plus de 1 ms lors de mes tests.

public static String docat2(String first, String second) {
  char[] f = first.toCharArray();
  char[] s = second.toCharArray();
  if (!first.contains("" + s[0]))
    return first + second;
  int idx = 0;
  try {
    while (!matches(f, s, idx)) idx++;
  } catch (Exception e) { }
  return first.substring(0, idx) + second;
}

private static boolean matches(char[] f, char[] s, int idx) {
  for (int i = idx; i <= f.length; i++) {
    if (f[i] != s[i - idx])
      return false;
  }
  return true;
}

Answer 2

Le plus simple : itérer sur la première chaîne en prenant des suffixes ("Some little d", "ome little d", "me little d"...) et tester la deuxième chaîne avec .startsWith . Lorsque vous trouvez une correspondance, concaténer le préfixe de la première chaîne avec la deuxième chaîne.

Voici le code :

String overlappingConcat(String a, String b) {                              
  int i;
  int l = a.length();
  for (i = 0; i < l; i++) {
    if (b.startsWith(a.substring(i))) {
      return a.substring(0, i) + b;
    }
  }
  return a + b;
}

Le plus gros problème d'efficacité ici est la création de nouvelles chaînes de caractères au moment de la mise en place de l'application. substring . Mise en œuvre d'une stringMatchFrom(a, b, aOffset) devrait l'améliorer, et est trivial.

Answer 3

Vous pouvez éviter de créer des sous-chaînes inutiles avec la méthode regionMatches().

public static String intersecting_concatenate(String a, String b) {
    // Concatenate two strings, but if there is overlap at the intersection,
    // include the intersection/overlap only once.

    // find length of maximum possible match
    int len_a = a.length();
    int len_b = b.length();
    int max_match = (len_a > len_b) ? len_b : len_a;

    // search down from maximum match size, to get longest possible intersection
    for (int size=max_match; size>0; size--) {
        if (a.regionMatches(len_a - size, b, 0, size)) {
            return a + b.substring(size, len_b);
        }
    }

    // Didn't find any intersection. Fall back to straight concatenation.
    return a + b;
}

Answer 4

Le code suivant semble fonctionner pour le premier exemple. Je ne l'ai pas testé de manière approfondie, mais vous avez compris l'essentiel. En gros, il recherche toutes les occurrences du premier caractère de la balise secondString dans le firstString puisque ce sont les seuls endroits possibles où un chevauchement peut se produire. Ensuite, il vérifie si le reste de la première chaîne est le début de la deuxième chaîne. Il est probable que le code contienne des erreurs lorsqu'aucun chevauchement n'est trouvé, ... mais c'était plus une illustration de ma réponse.

String firstString = "Some little d";
String secondString = "little dogs are so pretty";
String startChar = secondString.substring( 0, 1 );
int index = Math.max( 0, firstString.length() - secondString.length() );
int length = firstString.length();
int searchedIndex = -1;
while ( searchedIndex == -1 && ( index = firstString.indexOf( startChar, index ) )!= -1 ){
  if ( secondString.startsWith( firstString.substring( index, length ) ) ){
    searchedIndex = index;
  }
}
String result = firstString.substring( 0, searchedIndex ) + secondString;

Answer 5

isBlank(CharSequence) , join(T...) y left(String, int) sont des méthodes d'Apache Commons.

public static String joinOverlap(String s1, String s2) {
    if(isBlank(s1) || isBlank(s2)) { //empty or null input -> normal join
        return join(s1, s2);
    }

    int start = Math.max(0, s1.length() - s2.length());

    for(int i = start; i < s1.length(); i++) { //this loop is for start point
        for(int j = i; s1.charAt(j) == s2.charAt(j-i); j++) { //iterate until mismatch
            if(j == s1.length() - 1) { //was it s1's last char?
                return join(left(s1, i), s2);
            }
        }
    }

    return join(s1, s2); //no overlapping; do normal join
}