Coincidência de padrões (pattern matching)

1. Defina um função em C que implemente o algoritmo ingénuo para verificação de coincidência de padrões (naive search string).

2. Faça um programa que indique quantas vezes e em que shifts ocorre um padrão p na string t.

   ex:

   p=''123123''

   t=''123456712123123123124123123''

   p ocorre 3 vezes em t em: 9,12 e 21.

3. Defina uma função em C que implemente o algoritmo Rabin-Karp.

4. Resolva a alínea 2 com o algoritmo de Rabin-Karp

5. Desenhe os autómatos finitos que reconhecem os seguintes padrões (e construa as funções de transição), para o vocabulário {a,b,c,d}:
   1. p=''aaaaa''
   2. p=''ababa''
   3. p=''abcddcba''

6. Defina uma função em C que dado um padrão (uma string), e um vocabulário constrói a função de transição do autómato finito que reconhece o padrão.

7. Defina em C uma função que dado um padrão e um texto (duas strings) usa um autómato finito para encontrar o shift do padrão no texto.

8. Modifique a função da alínea anterior para encontrar todos os shifts do padrão no texto.