[Algoritmo C++] Anagramas

Mi problema no viene por ahí, pero si puede ayudar, aquí está mi constructor stringD:

#include <string>
#include <algorithm>
stringD::stringD(const std::string s):s1(s),s2(s) // s debe ser una palabra en mayúsculas
{
    std::sort(s2.begin(),s2.end());
}

-- La confianza no excluye el control

No entiendo tu algoritmo. Sin embargo, si tienes las letras de la palabra ordenadas alfabéticamente, basta con ver si las cadenas s2 son idénticas. Dos palabras son anagramas cuando contienen las mismas letras. Y si contienen las mismas letras, su orden alfabético es el mismo. Tu función debería ser simplemente: return s2==s.s2; -- Saludos! (deberías entender que SIEMPRE tengo razón) Char Snipeur

Estoy de acuerdo con la verdadera definición de un anagrama.
Sin embargo, como ya dije, entiendo por anagrama una palabra que se puede escribir con las letras de otra, por ejemplo si juego al Scrabble, tengo 7 letras y busco todas las palabras que pueda obtener con esas 7 letras.
Por lo tanto, en mis resultados habrá, por un lado, anagramas pero también palabras más cortas...

El problema es que mi algoritmo devuelve true para palabras this* que no contienen las letras de los s.
Lo que me deja aún más perplejo es que, con la misma palabra, si lanzo varias veces seguidas la búsqueda sobre el diccionario entero, no siempre me encuentra los mismos falsos positivos. Es decir, con la palabra "LETRAS" a veces obtengo 46 resultados positivos en el diccionario, a veces 64, a veces entre ambos... Claro está que los verdaderos "anagramas" siempre aparecen pero los falsos positivos parecen ir y venir de forma aleatoria!

Sobre la idea, mi algoritmo compara palabras que pueden ser de tamaño diferente this* de tamaño <= a s, por lo que mi primera línea. Por ejemplo, "BON" es -según mi definición- anagrama de "BONJOUR".
La búsqueda compara entonces this->s2="BNO" y s.s2="BJNOORU.
Recorro las dos palabras comparando las dos primeras letras, aquí son iguales -> comparo las segundas, diferentes -> incremento mi "cursor" sobre s.s2; para comparar O y O, excluyendo entonces la letra J.
Y sigo hasta el final, salvo si encuentro por ejemplo en lugar de J una P, lo que significaría que no hay O en s y que this no puede ser "anagrama" de s.

Parece que el problema proviene de mi return true; final, ya que aparentemente mis falsos positivos están formados por letras de s, y únicamente de letras superiores a la letra máxima de s!
Por ejemplo "LUTTEUR-ELRTTUU" es un falso positivo de "LETTRES-EELRSTT" formado con dos U superiores a la T, que era la última letra de EELRSTT...

Logro analizar el error, pero no veo cómo corregir mi problema, ni siquiera cómo abordarlo de otra forma...
--
La confianza no excluye el control

OK, entiendo mejor ahora. No había entendido tu primera explicación.
Como tus letras están ordenadas, ya es más fácil.
para que sea más claro, es mejor dividir tu bucle.

 bool stringD::isAnagram(stringD s) // ¿este* está escrito con las letras de s? { if (size()>s.size()) return false; int j=0; for (unsigned i=0; i<size(); i++) { while (s.s2[j]<s2[i]) j++; if (s2[i]!=s.s2[j]) return false; else j++; } return true; }

Pero también puedes hacer esto en pila. (escritura en algoritmo, no estoy seguro de las funciones utilizadas)

 bool stringD::isAnagram(stringD s) // ¿este* está escrito con las letras de s? { if (size()>s.size()) return false; for(int i=0;i<s.size();++i) { int pos=s.s2.find(s[i]); if(pos==std::string::npos) return false; else s2.remove(pos); } return true; } 

--
¡Saludo! (debe entenderse que siempre tienes razón)
Char Snipeur

Gracias, tu primer algoritmo no funciona mejor, pero partiendo de la idea del segundo algoritmo he logrado modificarlo y obtener los buenos resultados, y además con este método tengo la impresión de que podría prescindir del ordenamiento previo de las letras, lo que me ahorraría tiempo/memoria al cargar el diccionario.

bool stringD::isAnagram(stringD s) { if (size()>s.size()) return false; for(unsigned i=0;i<size unsigned="" pos="s.s2.find(s2[i]);" if="" return="" false="" else="" s.s2.erase="" true="">¡Gracias de nuevo! 
-- 
La confianza no excluye el control</size>