Ybadoo - Soluções em Software Livre
Tutoriais
Linguagens Formais e Autômatos

Desenvolva um programa, na linguagem de programação de sua preferência, que apresente as possíveis subpalavras da palavra fornecida pelo usuário.

 

Terminal

ybadoo@server:~$ ./application
Diagrama de Classes
Diagrama de Classes da Implementação na Linguagem de Programação Java

Arquivo Subfix.java

/*************************************************************************
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.lfa.tutorial01.topico07.exercicio02;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

/**
 * Classe responsavel pela geracao das subpalavras da palavra
 */
public class Subfix
{
  /**
   * Lista de subpalavras
   */
  private Set<String> subfixes;

  /**
   * Palavra
   */
  private String word;

  /**
   * Construtor para inicializar a palavra
   *
   * @param word palavra
   */
  public Subfix(String word)
  {
    this.word = word;

    subfixes = new TreeSet<String>(new Comparator<String>()
    {
      /* (non-Javadoc)
       * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
       */
      @Override
      public int compare(String sub1, String sub2)
      {
        if(sub1.length() < sub2.length())
        {
          return -1;
        }

        if(sub1.length() > sub2.length())
        {
          return 1;
        }

        return sub1.compareTo(sub2);
      }
    });

    subfixes.add("&");

    for(int length = 0; length < word.length(); length++)
    {
      for(int index = 0; index < (word.length() - length); index++)
      {
        subfixes.add(word.substring(index, length + index + 1));
      }
    }
  }

  /**
   * Retornar true se a subpalavra fornecida for uma subpalavra da palavra
   *
   * @param subfix subpalavra fornecido
   * @return true se a subpalavra fornecida for uma subpalavra da palavra
   */
  public boolean isSubfix(String subfix)
  {
    return subfixes.contains(subfix);
  }

  /**
   * Retornar a lista de subpalavras
   *
   * @return lista de subpalavras
   */
  public String[] list()
  {
    return subfixes.toArray(new String[0]);
  }

  /**
   * Retornar a quantidade de subpalavras
   *
   * @return quantidade de subpalavras
   */
  public int size()
  {
    return subfixes.size();
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    StringBuilder out = new StringBuilder();

    out.append("{");

    for(String subfix : subfixes)
    {
      if(subfix.length() != word.length())
      {
        out.append(subfix).append(", ");
      }
      else
      {
        out.append(subfix);
      }
    }

    out.append("}");

    return out.toString();
  }
}

Arquivo Application.java

/*************************************************************************
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.lfa.tutorial01.topico07.exercicio02;

import java.util.Scanner;

/**
 * Classe responsavel pela execucao da classe Subfix
 */
public class Application
{
  /**
   * Metodo principal da linguagem de programacao Java
   *
   * @param args argumentos da linha de comando (nao utilizado)
   */
  public static void main(String[] args)
  {
    Scanner scanner = new Scanner(System.in);

    System.out.print("Forneça a palavra desejada: ");
    String word = scanner.nextLine().trim();

    Subfix subfix = new Subfix(word);

    System.out.println("Observação: \"&\" representa a palavra vazia");
    System.out.print("Subpalavras: ");
    System.out.println(subfix);

    scanner.close();
  }
}

Saída da Implementação na Linguagem de Programação Java

Forneça a palavra desejada: ybadoo
Subpalavras: {&, a, b, d, o, y, ad, ba, do, oo, yb, ado, bad, doo, yba, adoo, bado, ybad, badoo, ybado, ybadoo}
Observação: & representa a palavra vazia