Comment trouver la séquence la plus courte d'astérisques séparant deux lettres distinctes dans une chaîne en utilisant des algorithmes STL?

Question

J'ai une chaîne comme ceci:

A*A**B***A**

Je suis intéressé par des séquences d'astérisques qui sont entre deux lettres distinctes, en particulier, je dois trouver la longueur de la plus courte telle séquence. Pour la chaîne ci-dessus, la réponse est, bien sûr, 2: A**B

Je peux facilement résoudre ce problème en utilisant une boucle traditionnelle, les gens dont je suis habitué à:

const string s = "A*A**B***A**"; 
string::size_type last_letter=-1, min_seq_len=s.size(); 
for(int i = 0; i < s.size(); i++) { 
    if(last_letter == -1 || s[i] == '*' || s[i] == s[last_letter]) { 
     if(s[i] != '*') { 
      last_letter = i; 
     } 
    } else { 
     min_seq_len = min(min_seq_len, i-last_letter-1); 
     last_letter = i; 
    } 
} 

Cependant, il est un moyen de le faire en utilisant le C++ algorithms library, itérateurs etc?

Je pose cette question parce que j'ai remarqué que j'ai de la difficulté à apprendre comment utiliser ces fonctions pour résoudre des problèmes d'algorithmes et que je trouve plus facile d'écrire des boucles à la main. Et je voudrais apprendre enfin fonctionner sur les algorithmes C, gammes, itérateurs etc.

Answer 1

Je suis intéressé par des séquences d'astérisques qui sont entre deux lettres distinctes, en particulier, je dois trouver la longueur de la plus courte une telle séquence.

1. Vous devez minimiser quelque chose. Vous pouvez utiliser std::min_element pour cela.

2. Ce quelque chose est un tas de morceaux "lettre + astérisques + lettre". Vous pouvez trouver des non-astérisques en utilisant std::find_if.

Vous devez ensuite écrire de la colle entre les algorithmes, que vous pouvez cacher derrière une interface de type STL. Exemple:

auto letter_pairs = letter_pair_generator(s); 
const auto min_seq_len = std::min_element(
    std::begin(letter_pairs), std::end(letter_pairs), 
    [](const auto& x) { return x.asterisk_count(); }); 

Lorsque letter_pair_generator est un adaptateur sur une std::string qui expose une interface de type conteneur qui retourne des paires de lettres distinctes avec des astérisques dans l'intervalle. Exemple:

string s = "A*A**B***A**"; 
for(const auto& p : letter_pair_generator(s)) cout << p; 

A * A ** B

A ** B

A ** B *** A

B *** A

---

au lieu que je trouve l'écriture des boucles à la main plus facile

Parfois, une boucle est plus claire et plus rapide que plusieurs appels à <algorithm>. Il n'y a rien de fondamentalement faux avec ça. Utilisez une boucle et enveloppez-la dans une interface plus sûre/plus agréable.

Answer 2

Je dois dire que je ne pouvais pas obtenir une énorme amélioration avec l'utilisation de la bibliothèque standard.Mais par exemple std::regex serait beaucoup plus simple s'il n'y avait pas d'exigence de lettres distinctes. En tout cas voici mes tentatives.

1. std::string::find_first_not_of utilisation

   int best = s.size(); 
   int prev = -1; 
   int next; 
   
   while ((next = s.find_first_not_of("*", prev+1)) >= 0) { 
       if (prev >= 0 && s[prev] != s[next]) { 
        best = min(best, next - prev - 1);    
       } 
       prev = next; 
   } 
   

Exécutable: https://ideone.com/xdhiQt

2. utilisation std::regex:

   regex r("(?=([^*][*]*[^*]))"); 
   
   int best = s.size(); 
   for (auto i = sregex_iterator(s.begin(), s.end(), r); i != sregex_iterator(); ++i) { 
       int pos = i->position(1); 
       int len = i->length(1); 
       if (s[pos] != s[pos + len -1]) { 
        best = min(len-2, best); 
       } 
   } 
   

Runnable: https://ideone.com/2UdRGG

Answer 3

Vous pouvez utiliser find_first_not_of de string pour cela aussi.

size_t min(str.length()), prev(0), found(0); 
while((found = str.find_first_not_of("*", prev)) != std::string::npos) { 
    if (str[found] != str[prev] && found - prev < min) { 
    min = found + 1 - prev; 
    } 
    prev = found + 1; 
} 

demo