 Autor
|
Tema: Duda algortirmo palabras circularmente iguales (Leído 3,175 veces)
|
Naster00
 Desconectado
Mensajes: 3
|
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
Mensajes: 1.211
|
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 ^^ : bool Coincidencia(const char* Correcta,const char* Palabra) { int Tamanyo = strlen(Correcta); int Indice = -1; // Si son de distinto tamanyo salimos if (Tamanyo != strlen(Palabra)) return false; // Buscamos la primera letra for (short i = 0; i < Tamanyo;i++) { if (Correcta[0] == Palabra[i]) { Indice = i; // Si la encontramos, apuntamos el indice ahi break; } } // Si no hemos encontrado el indice... if (Indice == -1) return false; // Empezamos la comparacion short j = 1; // La primera letra nos la saltamos for (short i = Indice+1; i != Indice;i++) { if (i == Tamanyo){ i = -1; continue;} if (Correcta[j] != Palabra[i]) return false; j++; } return true; }
|
|
|
|
« Última modificación: 3 Agosto 2013, 13:32 pm por amchacon »
|
En línea
|
|
|
|
Naster00
Desconectado
Mensajes: 3
|
Muchas gracias!! ya sé cómo es el algoritmo. Yo lo he programado así, es interesante ver cómo otros programan  bool CirculIgual(string uno, string dos){ bool res = true; if(uno.size() == dos.size()){ bool found = false; int dossize = dos.size(); int indice; for(int i = 0; i < dossize && !found; i++){ if (uno[0] == dos[i]){ indice = i; found = true; } } if(found){ int j = 1; for(int i = indice+1; i != indice && res;i++){ if(i == dossize) i = 0; if(uno[j] != dos[i]) res = false; j++; } } } else{ res = false; } return res; }
|
|
|
|
|
En línea
|
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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: #include <queue> using namespace std; bool Coincidencia(const char* Correcta,const char* Palabra) { queue<int> Indices; unsigned int Tamanyo = strlen(Correcta); // Si son de distinto tamanyo salimos if (Tamanyo != strlen(Palabra)) return false; // Buscamos la primera letra for (unsigned short i = 0; i < Tamanyo; i++) { if (Correcta[0] == Palabra[i]) { Indices.push(i); } } while (!Indices.empty()) { bool Done = true; int Valor = Indices.front(); // Empezamos la comparacion short j = 1; // La primera letra nos la saltamos for (unsigned short i = Valor+1; i != Valor; i++) { if (i == Tamanyo) { i = -1; continue; } if (Correcta[j] != Palabra[i]){ Done = false; break; } j++; } if (Done) return true; Indices.pop(); } return false; }
|
|
|
|
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
¡Buenas! Aquí te dejo otras dos formas de resolverlo: bool circulares(char *s1, char *s2) { int i = 0; bool ret = false; if(strlen(s1) != strlen(s2)) return false; if(!s1[0]) return true; while(s1[i++]) { if(!strcmp(s1,s2)) ret = true; char aux = s2[strlen(s2) - 1]; memmove(s2 + 1, s2, strlen(s2) - 1); s2[0] = aux; } return ret; } bool circulares(char *s1, char *s2) { char *aux = NULL; bool ret; if(strlen(s1) != strlen(s2)) return false; if(!s1[0]) return true; if(!(aux = new char[2 * strlen(s2) + 1])) return false; sprintf(aux,"%s%s",s2,s2); ret = strstr(aux,s1); delete [] aux; return ret; }
¡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
Mensajes: 3
|
Gracias de nuevo a los 2!
|
|
|
|
|
En línea
|
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Rnd iguales
Programación Visual Basic
|
monro
|
3
|
3,186
|
7 Abril 2010, 21:23 pm
por monro
|
|
|
|
IPs iguales
Dudas Generales
|
the_lokadio
|
9
|
6,688
|
24 Junio 2010, 13:25 pm
por the_lokadio
|
|
|
|
Duda: Crear una pila contando palabras encontradas en un string
PHP
|
Darkkz
|
2
|
2,678
|
10 Septiembre 2011, 23:35 pm
por Darkkz
|
|
|
|
[SOLUCIONADO] [DUDA] datos iguales en Atributos XML con SAX
Java
|
RyogiShiki
|
1
|
2,925
|
12 Noviembre 2011, 06:12 am
por RyogiShiki
|
|
|
|
duda con palabras clave y CPC
Dudas Generales
|
General Dmitry Vergadoski
|
0
|
2,975
|
2 Abril 2022, 22:59 pm
por General Dmitry Vergadoski
|
 |
