Trouver la première occurrence de n'importe quel symbole de la chaîne dans une autre chaîne

J'ai un problème: j'ai besoin de trouver la première occurrence de n'importe quel symbole de chaîne s2 (ou un tableau de char) dans la chaîne de s1.

Est-il fonction standard pour ce but? Si il n'y en a pas, ce qui est la bonne mise en œuvre de ce problème? (Bien sûr, je peux exécuter indexOf pour chaque char de mon s2, mais cela ne semble pas comme un bon algorithme, parce que si seul le dernier symbole se produit dans s1, nous devons courir à travers s1 |s2|-1 fois avant que je reçois une réponse).

Merci beaucoup!

  • Nope; la Java de la classe String n'a rien de ce genre. Pouvez-vous imaginer un meilleur algorithme que celui que vous décrivez?
  • Je emballer le caractère de la chaîne s2 dans un expression régulière par exemple, 'a|b|c|d" (les caractères spéciaux doivent être échappé) et ensuite utiliser Matcher.trouver des(..) pour obtenir la première occurrence.
  • Je doute que c'est plus rapide. À l'aide d'une expression régulière comme ça vous avez seulement besoin d'itérer une fois par le biais de la chaîne.
  • Bien que vous pourriez tout aussi bien parcourir manuellement vérifier si chaque personnage est dans le tableau de char (s2), qui serait encore plus rapide. Il va falloir faire des millions de fois, bien que pour l'une de ces être sensiblement différents.
  • J'ai posté un simpliste du fonctionnement de réponse qui montre comment il pourrait être fait à l'aide de regex comme @AndreHolzner suggère.
InformationsquelleAutor Finsky | 2011-11-14
  1. 5

    Mettre tous les caractères de s2 dans une constante de temps de recherche de la structure de données (par exemple,HashSet). Itérer sur chaque personnage dans s1 et de voir si votre structure de données contient que des caractères.

    Environ (non testé):

    public int indexOfFirstContainedCharacter(String s1, String s2) {
  Set<Character> set = new HashSet<Character>();
  for (int i=0; i<s2.length; i++) {
    set.add(s2.charAt(i)); //Build a constant-time lookup table.
  }
  for (int i=0; i<s1.length; i++) {
    if (set.contains(s1.charAt(i)) {
      return i; //Found a character in s1 also in s2.
    }
  }
  return -1; //No matches.
}

    Cet algorithme est O(n) par opposition à O(n^2) dans l'algorithme de vous décrire.

    InformationsquelleAutor maerics
  2. 3

    Ce que vous cherchez est indexOfAny de Apache StringUtils.

    Il ressemble à la mise en œuvre est:

     public static int indexOfAny(String str, char[] searchChars) {
   if (isEmpty(str) || ArrayUtils.isEmpty(searchChars)) {
     return -1;
   }
   for (int i = 0; i < str.length(); i++) {
     char ch = str.charAt(i);
       for (int j = 0; j < searchChars.length; j++) {
         if (searchChars[j] == ch) {
           return i;
         }
       }
     }
    return -1;
  }
    • La recherche linéaire? Ow, mieux vaut s'assurer que searchChars n'est jamais grand. J'ai pensé Apache serait de faire quelque chose d'un peu plus sophistiqué.
    InformationsquelleAutor Casey
  3. 3

    Ce que l'on entend par symbole dans ce contexte? Si c'est juste une 16-bits de Java char, c'est facile. Faire une table de recherche (array) pour toutes les valeurs possibles, en indiquant si elles apparaissent dans s2. Ensuite étape s1 jusqu'à ce que vous avez trouvé un symbole de s2 ou vous avez atteint la fin de la s1. Si un symbole est un code Unicode-point, c'est plus compliqué, mais le ci-dessus donne une méthode pour savoir où vous en avez besoin pour regarder de plus près.

    • tu veux dire, vous initialiser un tableau de 2^16 booléens où seuls les éléments correspondant à un caractère dans s2 sont mis à true ? (idée intéressante, je pense que HashSet pourrait effectuer presque aussi bien)
    • Oui, c'est l'idée. 2^16 est assez petite, donc il n'y a pas besoin d'utiliser de fantaisie comme HashSets, le tableau simple sera de le faire. Je ne suis pas assez familier avec la JVM, mais en C, je serais assez confiant que c'est aussi plus rapide, car il s'adapte confortablement dans L2 (normale du matériel). Ont été chars 20 bits ou plus, le tableau serait devenue trop grande, alors certainement un certain type de jeu.
    • Le domaine de clés est de petite taille 2^16 c'est donc un v de bonne réponse.
    InformationsquelleAutor Daniel Fischer