Casamento de Cadeias


Problema: Dadas duas cadeias (seqüências de símbolos) Y e X, determinar se Y é uma subcadeia de X, e em que posição de X a cadeia Y se encontra. Exemplos:
 
  • A cadeia "GAME" é uma subcadeia da cadeia "JULGAMENTO", começando na posição 4.
  • A cadeia "JUL" também é uma subcadeia de "JULGAMENTO", começando na posição 1.
  • A cadeia "JACA" não é uma subcadeia de "JULGAMENTO".
  • Algoritmo de Força Bruta

    int Sub(char * Y, char * X)
    {
        int i,j;
        bool casou;

        for(i=0;i <= (strlen(X)-strlen(Y));++i)
        {
             casou = true;
             for(j=0;j<strlen(Y);++j)
             {
                  if( Y[j] != X[i+j])
                  {
                       casou = false;
                       break;
                  }
             }
             if(casou) return(i+1); /* Para usar 1 (e não 0) como sendo a primeira posição da cadeia */
        }
        return(-1);  /* -1 esta sendo usado para indicar NÃO casamento */
    }

    Usando Sub:

    x = Sub("GAME","JULGAMENTO"); /* x receberá 4 */


    Complexidade no pior caso: O(nm), onde n = Tamanho de Y e m = Tamanho de X.

    A tabela abaixo mostra as comparações efetuadas pelo algoritmo da força bruta para
    Y = casaca
    X = casacocasasacadacasacaca

    As letras em negrito são aquelas em que Y[j] != X[i+j] (laço interno)

     
    Valores de i c a s a c o c a s a s a c a d a c a s a c a c a
    0 c a s a c a
    1 c
    2 c
    3 c
    4 c a
    5 c
    6 c a s a c
    7 c
    8 c
    9 c
    10 c
    11 c
    12 c a s
    13 c
    14 c
    15 c
    16 c a s a c a

    Algoritmo de Knuth, Morris e Pratt