Veremos um algoritmo bem interessante de manipulação de strings e com muitas aplicações práticas possíveis para seu uso, o LCS. LCS significa Longest Common Subsequence ou Maior Subsequência em Comum. É um algoritmo que utiliza como base para sua implementação PD (programação dinâmica), que é uma técnica que pode reduzir bastante o tempo de execução de diversos algoritmos com características de um problema possuir diversos subproblemas do mesmo tipo, e a PD não resolve esse problema duas vezes, deixando o código mais rápido. Problemas de Programação dinâmica têm duas formas comuns para serem resolvidos, ou resolvendo problemas menores para depois resolver os maiores, ou resolver os problemas maiores e depois os menores com memorização de resultados intermediários de problemas menores.

Uma subsequência de uma string “a” é qualquer string de mesmo tamanho ou menor, tal que a ordem em que os caracteres da substring estejam  na mesma ordem em que a original.

Uma substring comum a duas strings é uma substring das suas strings ao mesmo tempo, ou seja, uma string “abcde” e uma string “abacaxi” têm a seguinte substring em comum: “abc”. Já a string “xyz” e a string “zxy” têm 3 substrings em comum de mesmo tamanho (1), “x”, “y” e “z”. Ou seja caracteres podem aparecer em posições diferentes ou com caracteres intermediários, a subsequência será sempre caracteres presentes na mesma ordem em ambas as strings.

Esse algoritmo cria uma tabela de resultados onde, baseado nela, conseguimos navegar por ela sabendo qual caminho seguir para mostrar o caracter atual da substring comum.

Abaixo vou colocar uma implementação de código em C completo de uma LCS, a execução dele pede o número de casos que desejamos comparar. Digitando 1, por exemplo, o programa irá rodar uma vez só, depois ele pede uma string 1, basta digitar alguma string sem espaços (por exemplo: abc) ou uma string com espaço mas entre aspas (por exemplo: “abc def ghi”) depois uma outra string para comparação, a digitação segue a mesma regra da string 1. O resultado do algoritmo irá mostrar o tamanho da maior subsequência comum e na outra linha a substring gerada pelo algoritmo LCS.

#include<stdio.h>
#include<string.h>
#define MAX 100
char X[MAX],Y[MAX];
int i,j,m,n,c[MAX][MAX],b[MAX][MAX];
int LCSlenght()
{
  m = strlen(X);
  n = strlen(Y);

  for(i=1;i<=m;i++) c[i][0] = 0;
  for(j=0;j<=n;j++) c[0][j] = 0;
  for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
    {
      if(X[i-1]==Y[j-1])
      {
    c[i][j] = c[i-1][j-1]+1;
    b[i][j] = 1;
      }
      else if(c[i-1][j]>=c[i][j-1])
      {
    c[i][j] = c[i-1][j];
    b[i][j] = 2;
      }
      else
      {
    c[i][j] = c[i][j-1];
    b[i][j] = 3;
      }
    }
  return c[m][n];
}
void showLCS(int i, int j)
{
  if(i==0 || j==0)
   return;
  if(b[i][j]==1)
  {
    showLCS(i-1,j-1);
    printf("%c",X[i-1]);
  }
  else if(b[i][j]==2)
  {
    showLCS(i-1,j);
  }
  else
  {
    showLCS(i,j-1);
  }
}
int main()
{
  int num,i;
  printf("Digite quantas comparações deseja fazer (0 pra terminar): ");
  while(scanf("%d",&num)==1 && num>0)
  {
    for(i=0;i<num;i++)
    {
      printf("\nDigite a string 1: ");
      scanf("%s",X);
      printf("\nDigite a string 2: ");
      scanf("%s",Y);
      printf("Tamanho da LCS: %d ", LCSlenght());
      printf("\nResutado da LCS: ");
      showLCS(m,n);
      printf("\n");
    }
    printf("\nDigite quantas comparações deseja fazer (0 pra terminar): ");
  }
  return 0;
}

Esse algoritmo pode ser usado para fazer
correspondências de string de usuários com dados vindos de banco de dados, onde
o usuário pode esquecer de digitar algum caracter ou mesmo digitar coisas a
mais. Ou seja, uma aplicação pode ficar mais inteligente e menos complicada para
o usuário final.

Esse algoritmo tem muitas outras aplicações práticas na área de bioinformática, por exemplo. Ele também é a base dos algoritmos de comparação de arquivos, os famosos diff’s que usamos para ver em que parte do arquivo estão as diferenças para fazermos os merges apropriados.