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".
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 = casacocasasacadacasacacaAs 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
Função d(X,i)
Dada uma cadeia X= x1 x2
... xm e
um inteiro i , 1 <= i <= m, a
função d devolve o tamanho
do maior prefixo próprio de W= x1 x2
... xi
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
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 |
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