417 UVA word index

Word Index

Encoding schemes are often used in situations requiring encryption or information storage/transmission economy. Here, we develop a simple encoding scheme that encodes particular types of words with five or fewer (lower case) letters as integers.
Consider the English alphabet {a,b,c,...,z}. Using this alphabet, a set of valid words are to be formed that are in a strict lexicographic order. In this set of valid words, the successive letters of a word are in a strictly ascending order; that is, later letters in a valid word are always after previous letters with respect to their positions in the alphabet list {a,b,c,...,z}. For example,
abc aep gwz
are all valid three-letter words, whereas
aab are cat
are not.
For each valid word associate an integer which gives the position of the word in the alphabetized list of words. That is:

    a -> 1
    b -> 2
    .
    .
    z -> 26
    ab -> 27
    ac -> 28
    .
    .
    az -> 51
    bc -> 52
    .
    .
    vwxyz -> 83681

Your program is to read a series of input lines. Each input line will have a single word on it, that will be from one to five letters long. For each word read, if the word is invalid give the number 0. If the word read is valid, give the word's position index in the above alphabetical list.

Input

The input consists of a series of single words, one per line. The words are at least one letter long and no more that five letters. Only the lower case alphabetic {a,b,...,z} characters will be used as input. The first letter of a word will appear as the first character on an input line.
The input will be terminated by end-of-file.

Output

The output is a single integer, greater than or equal to zero (0) and less than or equal 83681. The first digit of an output value should be the first character on a line. There is one line of output for each input line.

Sample Input

z
a
cat
vwxyz

Sample Output

26
1
0
83681

Solución al problema C del Regional ACM ICPC Latin American 2012

Este fue uno de los problemas más resueltos durante el concurso. Pueden encontrar la redacción y subir sus códigos en:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=572&page=show_problem&problem=4144

Para resolverlo, una aproximación es construir el TRIE de las entradas marcando en cada nodo la cantidad de palabras que comparten el prefijo. Observamos entonces que es necesario teclear un caracter si es un caracter inicial o si en el TRIE el número de palabras que comparten el prefijo que estamos revisando es diferente al número correspondiente en el nodo padre. De este modo, podemos realizar una búsqueda en profundidad en el TRIE para contar la cantidad de teclas que es necesario presionar en total.

Una posible implementación comentada, es la siguiente:

#include<stdio.h>
long i,j,k,u,v,n;
char p[82];
double r;

struct nodo{
 long pre; // Numero de palabras que tienen el prefijo
 char pro; // Altura del nodo en el arbol
 long sig[28]; // Posicion de los nodos hijos en el arreglo
}T[1000004];

void a(){
 long in=0,no=0; // in es el indice del caracter, no es la posicion del nodo en que estamos dentro del arrelo
 while(p[in]){ // Mientras no lleguemos al final de la palabra
  if(T[no].sig[p[in]]){ // Si el prefijo ya esta, avanzamos a la posicion
   no=T[no].sig[p[in]];
  }else{ // Si no, creamos el nodo
   T[no].sig[p[in]]=u;
   no=u;
   u++;
  }
  T[no].pre++; // Aumentamos el contador de palabras con el prefijo
  T[no].pro=in; // Marcamos la altura del nodo
  in++;
 }
}

void dfs(long po, long rep){
 long ii;
 if(rep!=T[po].pre&&T[po].pro){ k=k+T[po].pre;  } // Si cambia la cantidad de palabras con el prefijo y no estamos en el primer caracter, agrega al contador el numero de palabras
 rep=T[po].pre; // Actualiza el numero de palabras con el prefijo que se esta revisando
 for(ii=1;ii<28;ii++){ // Revisamos todos los nodos hijos recursivamente
    if(T[po].sig[ii]){
     dfs(T[po].sig[ii],rep);
    }
  T[po].sig[ii]=false; // Aprovechando que estamos recorriendo todo en DFS, borramos lo necesario para el siguiente caso
  T[po].pre=0;
 }
}

int main(){
 while(scanf("%ld",&n)==1){
  u=1;
  for(i=0;i<n;i++){
   scanf("%s",p);
   j=0;
   while(p[j]){ p[j]=p[j]-'a'+1; j++;  } // Asignamos a las letras de la a a la z un numero del 1 al 26 para facilitar su manejo
   a(); // Agregamos la palabra al TRIE
  }
  k=0; // Inicializamos el contador k
  v=0;
  dfs(0,v);
  r=double(k+n)/double(n);
  printf("%.2lf\n",r);
 }
}

Funciones de lectura y escritura y el algoritmo KMP

Dejo el link a un breve resumen de algunas funciones de lectura y escritura en C/C++ (un texto muy introductorio) y a una corta reseña sobre el algoritmo Knuth-Morris-Pratt, que encuentra todas las ocurrencias de una subcadena en una cadena de caracteres en tiempo lineal sobre la longitud de la cadena. Recomiendo ampliamente resolver los problemas propuestos con el KMP, con el fin de practicar su implementación y conseguir una mejor comprensión del funcionamiento del algoritmo.

https://docs.google.com/file/d/0B6M0ckH75hxIbkRfNlpsc2M2S1k/edit?usp=sharing

https://docs.google.com/file/d/0B6M0ckH75hxIRGFpXzNkQmlocTA/edit?usp=sharing

UVA 10298 Power Strings

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Sample Input

abcd
aaaa
ababab
.

Output for Sample Input

1
4
3

Manejo de cadenas de caracteres

Un poco acerca del manejo de caracteres:

https://docs.google.com/file/d/0B0ZpbtK9Vuz1N1J5bW1NZHV1eTA/edit?usp=sharing