OBI 2017 - Palíndroma

Esta é a resolução da questão 2 da prova da fase Universitária da OBI-2017, que consiste em verificar o número mínimo de palíndromas que uma string pode ser dividida. A string é chamada de palíndroma se a sequência de caracteres da esquerda para a direita é igual à sequência da direita pra esquerda. Quando uma palavra não for palíndroma, devemos subdividi-la em partes menores (substrings) que sejam palíndromas.

Primeiramente, criaremos uma função para verificar se a sequência forma uma palíndroma e, caso não for, retornar um valor lógico falso.

int pali(int tam, char *nome){
int i,ok=1,j=tam-1;
for(i=0;i<tam/2;i++){
    if(nome[i]!=nome[j]){
        ok=0;
        break;}
    j--;}
 return ok;
} 

Após isto devemos pensar na subdivisão da entrada em substrings, ou seja, gerar todas as substrings e verificar se formam palíndromas e  armazená-las em uma variável global. Por fim retornará a quantidade total das substrings. A cada repetição do laço, geraremos uma substring e toda vez que ela for palíndroma, armazenaremos ela na matriz palíndroma.

int gera_todas_pali(int tam, char *nome){
int i,j,k=0,r,t;
char aux[tam+1];
for(i=0;i

Agora precisamos encontrar o menor número de conjuntos possíveis. Em nossa primeira condição, iremos comparar se a nossa substring pertence a posição atual da sequência, na segunda verificamos se essa substring é maior, e caso ela for utilizaremos a função 'substring' para verificar se ela encaixa na sequência. Na terceira condição, verificamos se elas são as mesmas. Por fim, incrementamos o contador i com o tamanho da substring e o total.

int verifica_menor_palindroma(int k, int tam, char *str){
int i=0,j,maior,total=0;
char aux[MAX];
while(i<tam){
  maior=0;
  for(j=0;j<k;j++){
    if(palindroma[j][0]==str[i]){
      int t=strlen(palindroma[j]);
      if(t>maior){
       substring(str, aux, i, t);
       int ok=strcmp(aux,palindroma[j]);
 if(!ok){
          maior=t;
        }}}}
    i+=maior;
   total++;}
return total;
}

A função verifica_menor_palindroma utiliza a função substring.

void substring(char *s, char *sub, int p, int l) {
   int c = 0;
 
   while (c < l) {
      sub[c] = s[p+c];
      c++;
   }
   sub[c] = '\0';
}

Pronto terminamos, agora só é preciso fazer as leituras e chamar as funções na função principal main.

Coded by: André da Cunha Ribeiro.