elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recopilación Tutoriales y Manuales Hacking, Seguridad, Privacidad, Hardware, etc


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Duda algortirmo palabras circularmente iguales
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Duda algortirmo palabras circularmente iguales  (Leído 2,794 veces)
Naster00

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Duda algortirmo palabras circularmente iguales
« en: 3 Agosto 2013, 11:17 am »

Tengo que hacer una función que reciba dos cadenas de caracteres cualesquiera y devuelva (cierto o falso) si son circularmente iguales. Son circularmente iguales si ambas contienen exactamente los mismos caracteres, y ordenados de la misma forma, pero empezando por puntos distintos. Por ejemplo: "aviacion" y "cionavia".

He estado probando y no me sale, no se me ocurre un algoritmo que funcione con cualquier par de palabras. ¿Alguien me puede echar un cable? Me vale pseudocódigo, el problema es que no se me ocurre el algoritmo, no la programación en C++ en sí.
Gracias.


En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Duda algortirmo palabras circularmente iguales
« Respuesta #1 en: 3 Agosto 2013, 13:25 pm »

Muy interesante.

Lo primero sería encontrar la primera letra de la palabra (en este caso la a). Posteriormente iría comprobando el resto de las letras, en el momento que una sea diferente devuelvo falso.

Me ha picado la curiosidad y lo he elaborado yo mismo ^^ :

Código
  1. bool Coincidencia(const char* Correcta,const char* Palabra)
  2. {
  3.    int Tamanyo = strlen(Correcta);
  4.    int Indice = -1;
  5.  
  6.    // Si son de distinto tamanyo salimos
  7.  
  8.    if (Tamanyo != strlen(Palabra)) return false;
  9.  
  10.    // Buscamos la primera letra
  11.  
  12.    for (short i = 0; i < Tamanyo;i++)
  13.    {
  14.        if (Correcta[0] == Palabra[i])
  15.        {
  16.            Indice = i; // Si la encontramos, apuntamos el indice ahi
  17.            break;
  18.        }
  19.    }
  20.  
  21.    // Si no hemos encontrado el indice...
  22.  
  23.    if (Indice == -1) return false;
  24.  
  25.    // Empezamos la comparacion
  26.  
  27.    short j = 1; // La primera letra nos la saltamos
  28.  
  29.    for (short i = Indice+1; i != Indice;i++)
  30.    {
  31.        if (i == Tamanyo){ i = -1; continue;}
  32.  
  33.        if (Correcta[j] != Palabra[i]) return false;
  34.  
  35.        j++;
  36.    }
  37.  
  38.    return true;
  39. }


« Última modificación: 3 Agosto 2013, 13:32 pm por amchacon » En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Naster00

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Duda algortirmo palabras circularmente iguales
« Respuesta #2 en: 3 Agosto 2013, 14:05 pm »

Muchas gracias!! ya sé cómo es el algoritmo.
Yo lo he programado así, es interesante ver cómo otros programan ;D
Código
  1. bool CirculIgual(string uno, string dos){
  2. bool res = true;
  3. if(uno.size() == dos.size()){
  4. bool found = false;
  5. int dossize = dos.size();
  6. int indice;
  7. for(int i = 0; i < dossize && !found; i++){
  8. if (uno[0] == dos[i]){
  9. indice = i;
  10. found = true;
  11. }
  12. }
  13. if(found){
  14. int j = 1;
  15. for(int i = indice+1; i != indice && res;i++){
  16. if(i == dossize)
  17. i = 0;
  18. if(uno[j] != dos[i])
  19. res = false;
  20. j++;
  21. }
  22. }
  23.  
  24. } else{
  25. res = false;
  26. }
  27. return res;
  28. }
  29.  
En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Duda algortirmo palabras circularmente iguales
« Respuesta #3 en: 3 Agosto 2013, 14:59 pm »

Hay un problema en nuestro algoritmo, no funciona correctamente si compara palabras como "tomate" y "tetoma" (esto sucede porque hay varias T).

He modificado un poco el codigo. Ahora comprueba con todas las "t" que se encuentre:

Código
  1. #include <queue>
  2.  
  3. using namespace std;
  4.  
  5. bool Coincidencia(const char* Correcta,const char* Palabra)
  6. {
  7.    queue<int> Indices;
  8.    unsigned int Tamanyo = strlen(Correcta);
  9.  
  10.    // Si son de distinto tamanyo salimos
  11.  
  12.    if (Tamanyo != strlen(Palabra)) return false;
  13.  
  14.    // Buscamos la primera letra
  15.  
  16.    for (unsigned short i = 0; i < Tamanyo; i++)
  17.    {
  18.        if (Correcta[0] == Palabra[i])
  19.        {
  20.            Indices.push(i);
  21.        }
  22.    }
  23.  
  24.  
  25.    while (!Indices.empty())
  26.    {
  27.        bool Done = true;
  28.  
  29.        int Valor = Indices.front();
  30.  
  31.        // Empezamos la comparacion
  32.  
  33.        short j = 1; // La primera letra nos la saltamos
  34.  
  35.        for (unsigned short i = Valor+1; i != Valor; i++)
  36.        {
  37.            if (i == Tamanyo)
  38.            {
  39.                i = -1;
  40.                continue;
  41.            }
  42.  
  43.            if (Correcta[j] != Palabra[i]){ Done = false; break; }
  44.  
  45.            j++;
  46.        }
  47.  
  48.        if (Done) return true;
  49.  
  50.        Indices.pop();
  51.    }
  52.    return false;
  53. }
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Duda algortirmo palabras circularmente iguales
« Respuesta #4 en: 3 Agosto 2013, 20:39 pm »

¡Buenas!

Aquí te dejo otras dos formas de resolverlo:

Código
  1. bool circulares(char *s1, char *s2)
  2. {
  3.    int i = 0;
  4.    bool ret = false;
  5.  
  6.    if(strlen(s1) != strlen(s2))
  7.        return false;
  8.  
  9.    if(!s1[0])
  10.        return true;
  11.  
  12.    while(s1[i++])
  13.    {
  14.        if(!strcmp(s1,s2))
  15.            ret = true;
  16.  
  17.        char aux = s2[strlen(s2) - 1];
  18.        memmove(s2 + 1, s2, strlen(s2) - 1);
  19.        s2[0] = aux;
  20.    }
  21.  
  22.    return ret;
  23. }
  24.  
  25. bool circulares(char *s1, char *s2)
  26. {
  27.    char *aux = NULL;
  28.    bool ret;
  29.  
  30.    if(strlen(s1) != strlen(s2))
  31.        return false;
  32.  
  33.    if(!s1[0])
  34.        return true;
  35.  
  36.    if(!(aux = new char[2 * strlen(s2) + 1]))
  37.        return false;
  38.  
  39.    sprintf(aux,"%s%s",s2,s2);
  40.  
  41.    ret = strstr(aux,s1);
  42.  
  43.    delete [] aux;
  44.  
  45.    return ret;
  46. }
  47.  

¡Saludos!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
Naster00

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Duda algortirmo palabras circularmente iguales
« Respuesta #5 en: 5 Agosto 2013, 11:34 am »

Gracias de nuevo a los 2!
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Rnd iguales
Programación Visual Basic
monro 3 2,685 Último mensaje 7 Abril 2010, 21:23 pm
por monro
IPs iguales
Dudas Generales
the_lokadio 9 5,792 Último mensaje 24 Junio 2010, 13:25 pm
por the_lokadio
Duda: Crear una pila contando palabras encontradas en un string
PHP
Darkkz 2 2,485 Último mensaje 10 Septiembre 2011, 23:35 pm
por Darkkz
[SOLUCIONADO] [DUDA] datos iguales en Atributos XML con SAX
Java
RyogiShiki 1 2,761 Último mensaje 12 Noviembre 2011, 06:12 am
por RyogiShiki
duda con palabras clave y CPC
Dudas Generales
General Dmitry Vergadoski 0 2,256 Último mensaje 2 Abril 2022, 22:59 pm
por General Dmitry Vergadoski
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines