3.1 Algoritmul forţei brute

Metoda evidentă pentru găsirea şabloanelor este de a verifica pentru fiecare poziţie în text, dacă şablonul se află la acea poziţie. Pseudocodul pentru acest algoritm care returnează prima poziţie a şirului (şablonului) p în şirul (textul) a este prezentat mai jos:

01: FORŢĂ-BRUTĂ(p, a) 02:   M ← lungime(p) 03:   N ← lungime(a) 04:   pentru i ← 0, N şi j ← 0, M 05:     dacă a[i] ≠ p[j] 06:        i ← i - (j - 1) 07:        j ← -1 08:   dacă j = M 09:     returnează i - M 10:   altfel 11:     returnează i

Programul memorează un index (i) în text şi un altul (j) în şablon. Cât timp ei indică spre caractere identice, ambii sunt incrementaţi. În caz contrar, j este resetat, astfel încât să indice spre începutul şablonului, iar i este resetat astfel încât să indice corespunzător deplasării cu o poziţie spre dreapta în text.

Dacă s-a ajuns la sfârşitul şablonului (j = M), atunci s-a găsit o apariţie a acestuia în text, la poziţia a[i - M]. Altfel, dacă se ajunge la sfârşitul textului mai întâi, (i = N), nu există o asemenea potrivire: şablonul nu apare în text, algoritmul returnând valoarea N.

Într-o aplicaţie de editare de text, "bucla interioară" este rareori iterată şi timpul de rulare este aproape proporţional cu numărul de caractere examinate.

Pe de altă parte, acest algoritm poate fi foarte "încet" pentru anumite şabloane, de exemplu dacă şirul este binar, cum s-ar putea întâlni în procesarea imaginilor sau în programarea aplicaţiilor de sistem. Următoarea figură ilustrează un asemenea caz, considerând căutarea şirului 10100111 într-un text binar lung:

Figura 3.1.1 Algoritmul forţei brute aplicat pe un text binar

Fiecare linie (exceptând ultima, care arată potrivirea) se constituie din zero sau mai multe caractere care se potrivesc şablonului, urmate de o nepotrivire. Acestea sunt "începuturile false", care nu pot fi evitate în acest algoritm, iar un scop evident în proiectarea algoritmilor este de a limita numărul şi lungimea acestora. Pentru acest exemplu, în medie cam 1 - 2 caractere sunt examinate, cu toate că situaţia poate fi mai rea.

Proprietatea 3.1.1: Algoritmul forţei brute are complexitatea Θ(MN).
Cazul cel mai defavorabil este atunci când atât textul cât şi şablonul sunt alcătuite din 0-uri, urmate de un 1. În acest caz, pentru fiecare din cele N - M + 1 potriviri posibile, toate caracterele din şablon sunt verificate în text, deci M(N - M + 1) comparaţii. În mod normal, M este mic în comparaţie cu N, rămânând un cost total de aproximativ NM.

Asemenea şiruri "degenerate" sunt puţin probabile într-o limbă, sau chiar într-un limbaj de programare, însă pot apărea destul de des în prelucrarea imaginilor, deci căutăm algoritmi mai buni.

Este prezentată în continuare implementarea algoritmului în C++, datorită largii răspândiri pe care acest limbaj de programare o cunoaşte, şi pentru a da o soluţie practică imediată:

01: int fortabruta(char *p, char *a) 02: { 03:   int i, j, m = strlen(p), n = strlen(a); 04:   for(i = 0, j = 0; j < m && i < n; i++, j++) 05:     if(a[i] != p[j]) 06:     { 07:        i -= j - 1; 08:        j = -1; 09:     } 10:   return ( j == m ? i - m : i ); 11: }

Listing 3.1.1 Implementarea algoritmului forţei brute în limbajul C++