Lista5

Prévia do material em texto

1.
(a) “Teste de arquivo invertido. Teste com texto invertido. Base de teste para arquivo invertido.”
Teste 1, 29, 64.
De 7, 61.
arquivo 10, 75.
invertido 18, 45, 83.
com 35.
texto 39.
base 56.
Para 70.
(b) No caso de um arquivo invertido, é feito uma tabela, onde serão registradas as posições de ocorrências de cada palavra na frase. Ao efetuar um busca por palavra, primeiramente a palavra é pesquisada na tabela, e assim, as suas posições de ocorrências são retornadas. No caso de uma busca por frase, ao se encontrar uma palavra, o algoritmo irá somar a quantidade de letras da palavra com a sua posição, e assim verificar se a palavra que segue no texto, é a palavra a ser buscada.
2.
PADRÃO: AFED Base: 3
Referência ASCII:
A = 65; F = 70; E = 69; D = 68; X = 88; Y = 89; Z = 90
Referência ao padrão AFED: 65*3³+70*3²+69*3+68=2660
Referências para as palavras a serem buscadas:
AFAF: 2650
FAFE: 2754
AFED: 2660
FEDX: 2803
EDXY: 2828
DXYZ: 29852
Ocorreu o casamento na posição 2, o que foi verificado com os números da tabela hash que combinam! Agora é feito uma verificação letra a letra para verificar se realmente ocorre a presença do padrão.
3.
a)
i 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
P[i] 
a 
b 
r 
a 
c 
a 
d 
a 
b 
r 
a 
π[i] 
0 
0 
0 
1 
0 
1 
0 
1 
2 
3 
4 
b)
	a b r c c a d a b r a c a c a a b r a c a d a b r a a b r a b r a c a d a
	a b r a c a d a b r a
	-- -- -- a b r a c a d a b r a
	-- -- -- -- a b r a c a d a b r a
	-- -- -- -- -- a b r a c a d a b r a
	-- -- -- -- -- -- a b r a c a d a b r a
	-- -- -- -- -- -- -- a b r a c a d a b r a
	-- -- -- -- -- -- -- -- -- -- -- - a b r a c a d a b r a
	-- -- -- -- -- -- -- -- -- -- -- -- - a b r a c a d a b r a
	-- -- -- -- -- -- -- -- -- -- -- -- -- - a b r a c a d a b r a 
	-- -- -- -- -- -- -- -- -- -- -- -- -- -- - a b r a c a d a b r A
	-- -- -- -- -- -- -- -- -- -- -- -- -- -- - -- -- -- -- -- -- -- a b r a c a d a b R A
	-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - -- -- -- -- -- -- -- -- -- A B R A C A D A B R A
	-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --A B R A C A D A B R A 
Casamento na posição 16!
4.
a)
ABRACADABRA
D[a]=3 D[b]=2 D[r]=1 D[c]=6 D[d]=4
b)
	a
	b
	r
	c
	c
	a
	d
	a
	b
	r
	a
	c
	a
	c
	a
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	a
	b
	r
	a
	b
	r
	a
	c
	a
	d
	a
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	a
	b
	r
	a
	c
	a
	d
	a
	b
	r
	a
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	a
	b
	r
	a
	c
	a
	d
	a
	b
5. Porque em seu pior caso, o algoritmo percorre todo o alfabete, sendo o alfabeto tamanho n, a ordem do algoritmo será O(n); 
6. #include <stdio.h>
#include <math.h>
int ascii(char caracter)
{
 int limite=128;
 int ascii_v= (int) caracter;
 if(ascii_v>limite) return -1;
 return (int) caracter; //Retorna o valor ascii do caracter
}
int RK(int base, char *palavra, char *texto,int vetor[],int *tam_vetor)
{
 long unsigned int hash_padrao=0,hash_pal=0;
 int pos_vet=0;
 int i,j,k,tam_pal=strlen(palavra),tam_texto=strlen(texto);
 for(i=0;i<tam_pal;i++)
 {
 if(ascii(palavra[i])==-1) return -1;
 hash_padrao=hash_padrao + ascii(palavra[i])*( pow( base,( tam_pal-i-1) ) );
 }
 
 for(i=0;i<tam_texto;i++)
 {
 for(k=0;k<tam_pal;k++)
 {
 if(ascii(texto[k+i])==-1) return -1;
 hash_pal=hash_pal + ascii(texto[k+i])*( pow( base,( tam_pal-k-1) ) );
 }
 if(hash_pal==hash_padrao)
 {
 vetor[pos_vet]=i+1;
 pos_vet++;
 }
 hash_pal=0;
 }
 *tam_vetor=pos_vet;
 return 0;
}
main()
{
 char pal[10], sent[100];
 int vetor[10],ocorrencias=0,i;
 printf("Digite a frase:");
 fgets(sent,100,stdin);
 printf("Digite a palavra:");
 scanf("%s",&pal);
 if(RK(3,pal,sent,vetor,&ocorrencias)==-1) printf("Vocabulario ultrapassa o limite estabelecido..."); //Executa a funcao e verifica o limite
 if(ocorrencias>0) printf("Ocorreu na(s) posicao(oes):\n");
 for(i=0;i<ocorrencias;i++) printf("%d ",vetor[i]); //Imprime as ocorrencias existentes no vetor passado por referencia
 printf("\n");
 system("pause");
 return;
}
7.
#include<stdio.h>
#include<string.h>
 
char T[50];
kmp(char *p_palavra, char *p_sentenca, int tamanho_palavra, int tamanho_sentenca)
{
 int pos;
 int m=0;
 int i=0;
 int aux = 1;
 for(;m<tamanho_sentenca;)
 {
 if(*(p_palavra+i) == *(p_sentenca+m+i))
 {
 i=i+1;
 if(i==tamanho_palavra)
 {
 pos=m+1;
 printf("A palavra foi encontrada na posicao %d\n",pos);
 aux = 0;
 }
 }
 else
 {
 m=m+i-T[i];
 if(i>0)
 i=T[i];
 
 }
 }
 if (aux) printf("Nao foi encontrado!\n");
 return tamanho_sentenca;
}
 
 
aux_pi(char *p_palavra, char *p_sentenca, int tamanho_palavra, int tamanho_sentenca)
{
 int i,j;
 i=2;
 j=0;
 T[0]=-1;
 T[1]=0;
 for(;i<tamanho_palavra; )
 {
 if(*(p_palavra+i-1) == *(p_palavra+j))
 {
 T[i]=j+1;
 i=i+1;
 j=j+1;
 }
 else if(j>0)
 {
 j=T[j];
 }
 else
 {
 T[i]=0;
 i=i+1;
 }
 }
}
main()
{
 char pal[10], sent[40], *p_pal, *p_sent;
 int tam_pal, tam_sent;
 p_pal = pal;
 p_sent = sent;
 
 printf("Digite a frase:");
 fgets(sent,40,stdin);
 
 printf("Digite a palavra:");
 
 scanf("%s",&pal);
 tam_pal = strlen(pal);
 tam_sent = strlen(sent);
 aux_pi(p_pal,p_sent,tam_pal,tam_sent);
 kmp(p_pal,p_sent,tam_pal,tam_sent);
 system("pause");
 return;
}
 
8.
#include <stdio.h>
void BMH(char T[], long n, char P[], long m)
{ 
 long i, j, k, d[255 + 1];
 for (j = 0; j <= 256; j++) 
 d[j] = m;
 for (j = 1; j < m; j++) 
 d[P[j-1]] = m - j;
 i = m;
 while (i <= n) 
 { 
 k = i;
 j = m;
 while (T[k-1] == P[j-1] && j > 0)
 {
 k--; 
 j--; 
 }
 if (j == 0) printf("Encontrado na posicao: %3ld\n", k + 1);
 i += d[T[i-1]];
 }
}
main()
{ 
 char pal[10], sent[100], *p_pal, *p_sent;
 int tam_pal, tam_sent;
 
 p_pal = pal;
 p_sent = sent;
 printf("Digite a frase:");
 fgets(sent,100,stdin);
 printf("Digite a palavra:");
 scanf("%s",&pal);
 tam_pal = strlen(pal);
 tam_sent = strlen(sent);
 BMH(sent, tam_sent, pal, tam_pal);
 system("pause");
 return;
}