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

Definições Auxiliares:
 
• Um prefixo de uma cadeia X = x₁ x₂ ... x_m é uma outra cadeia P = x₁ x₂ ... x_k em que 0 <= k <= m

Eg.: prefixos de "TOMATE" = {"","T","TO","TOM","TOMA","TOMAT","TOMATE"}
• Um sufixo de uma cadeia X = x₁ x₂ ... x_m é uma outra cadeia S = x_k x_k+1 ... x_m em que 0 <= k <= m

Eg.: sufixos de "TOMATE" = {"","E","TE","ATE","MATE","OMATE","TOMATE"}
• Sufixos e prefixos próprios são aqueles que NÃO são iguais a própria palavra


Função d(X,i)
Dada uma cadeia X= x₁ x₂ ... x_m e um inteiro i , 1 <= i <= m, a função d devolve o tamanho do maior prefixo próprio de W= x₁ x₂ ... x_i que coincide com um sufixo de W

Por exemplo, d("TATUATATATUABA",8) = 3, visto que, W = "TATUATAT", e o prefixo "TAT" é o maior em W que coincide com um sufixo.

Já d("TATUATATATUABA",1) = 0, visto que, W = "T" e o único prefixo próprio de W é a cadeia vazia "".

Outros valores d para X = "TATUATATATUABA"

d(X,1) = 0
d(X,2) = 0
d(X,3) = 1 "T"
d(X,4) = 0
d(X,5) = 0
d(X,6) = 1 "T"
d(X,7) = 2 "TA"
d(X,8) = 3 "TAT"
d(X,9) = 2 "TA"
d(X,10) = 3 "TAT"
d(X,11) = 4 "TATU"
d(X,12) = 5 "TATUA"
d(X,13) = 0
d(X,15) = 0

Valores d para X = "casaca"

d(X,1) = 0
d(X,2) = 0
d(X,3) = 0
d(X,4) = 0
d(X,5) = 1 "c"
d(X,6) = 2 "a"

Atenção:

d("aaaaaa",6) = 5

O Algoritmo

/* Estou assumindo que os índices de vetores começam em 0 */

int Sub(char * Y, char * X)
{
    i = j = 0;
    while( i-j <= n-m)
    {
        casando = true;
        while( j < m && casando)
        {
            if( X[i] == Y[j] )
            {
                ++i; ++j;
            }
            else casando = false;
        }
        if( casando ) return(i-m+1);
        if( j == 0 ) ++i;
        else j = d(X,j);
    }
    return(-1);
}

Exemplo 1: Sub("casaca","casacoacacasaca");
 

c

a

s

a

c

o

a

c

a

c

a

s

a

c

a

c

a

s

a

c

a

a

c

c

c

a

s

c

a

s

a

c

a

Variação nos valores (i,j) : (0,0) - (1,1) - (2,2) - (3,3) - (4,4)  - (5,5) - (5,1) - (5,0) - (6,0) - (7,0) - (8,1) - (9,2) - (9,0) - (10,1) - (11,2) - (12,3) - (13,4) - (14,5)

Exemplo 2: Sub("abaabau","abaabaabaabaabaabaua");

d(X,1) = 0
d(X,2) = 0
d(X,3) = 1
d(X.4) = 1
d(X,5) = 0
d(X,6) = 3
d(X,7) = 0
 

a

b

a

a

b

a

a

b

a

a

b

a

a

b

a

a

b

a

u

a

a

b

a

a

b

a

u

a

b

a

u

a

b

a

u

a

b

a

u

a

b

a

u


 Links interessantes sobre casamento de cadeias:

http://www.mat.unb.br/~ayala/TCgroup/PatternMatching/kmpbm.html
http://www1.ics.uci.edu/~eppstein/161/960222.html
Algoritmo de Knuth, Morris e Pratt