Optimizarea consta in construirea automatului finit determinist asociat celor $N$ cuvinte. Acest automat poate fi construit in complexitate $O(N*L)$, conform algoritmului 'Aho-Corasick':http://www.softlab.ntua.gr/facilities/public/AD/DM/Algorithms%20for%20Finding%20Patterns%20in%20Strings.html. Modul de constructie este asemanator calculului functiei prefix din algoritmul 'KMP':http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm. Construim trie-ul cuvintelor, apoi, pentru un nod $X$ al trie-ului, determinam nodul din trie care corespunde celui mai lung sir de caractere care este sufix al sirului asociat nodului $X$. Putem calcula aceste valori pe nivele, intrucat un nod $Y$ de tipul celui mentionat mai sus se va afla intotdeauna pe un nivel superior nodului $X$ (dar nu neaparat pe calea de la radacina trie-ului pana la nodul $X$). Acest automat se poate folosi apoi in cadrul parcurgerii textului dat. Incepem din starea corespunzatoare sirului vid (radacina trie-ului). De fiecare data cand trecem la urmatorul caracter, incercam sa trecem in nodul din trie ce corespunde caracterului respectiv si este fiu al starii curente. Daca acest nod nu exista, la fel ca la KMP, trecem in starea corespunzatoare "prefixului-sufix" al starii curente si repetam acest lucru pana cand ajungem in radacina trie-ului sau intr-un nod care are un fiu ce corespunde caracterului urmator din sir. Daca ajungem intr-un nod ce corespunde unei stari finale, atunci am gasit o aparitie a unui cuvant.

Solutia oficiala foloseste un algoritm de constructie a unui 'automat finit determinist':http://en.wikipedia.org/wiki/Deterministic_finite_state_machine avand complexitate $O(N*L^2^)$. Se va construi trie-ul cuvintelor, apoi, pe baza acestui trie, se va calcula un automat care are un numar de stari egal cu numarul de noduri ale trie-ului. Pentru fiecare stare $X$ si fiecare caracter $c$, se va calcula functia $nextState[X,c]$, reprezentand starea ce corespunde celui mai lung sir care este un subsir al sirului corespunzator starii $X$ concatenat cu caracterul $c$. Pentru starile $X$ ce au fiu in trie corespunzator unui caracter $c$, $nextState[X,c]$ va fi egal cu acest fiu. Pentru celelalte caractere si o stare $X$, vom avea $O(L)$ stari candidate. Mai exact, sa consideram ca $TX$ este tatal nodului $X$ in trie (presupunand ca $X$ nu este radacina trie-ului) si ca avem starile $Q{~0~}, Q{~1~}, .., Q{~P~}$ stari ce corespund sufixelor de lungime $0, 1, .., P$ ale sirului corespunzator nodului $TX$ (acest sir are $P+1$ caractere). Atunci multimea de stari $R{~1~}, .., R{~P+1~}$ avand aceeasi semnificatie pentru nodul $X$ se calculeaza ca fiind $R{~1~}=fiu[Q{~0~},u], R{~2~}=fiu[Q{~1~},u], .., R{~P+1~}=fiu[Q{~P~},u]$, unde $X=fiu[TX,u]$, adica fiul nodului $TX$, ce corespunde caracterului u. La aceasta multime vom adauga pe R$0$=radacina trie-ului (ce corespunde sirului vid). $nextState[X,c]$ va fi egal cu sirul de lungime maxima dintre sirurile corespunzatoare nodurilor $fiu[R{~i~},c]$, cu $0 ≤ i ≤ P+1$. Se observa usor ca pentru orice nod $X$ pot exista cel mult $O(L)$ stari candidate, deoarece sirul corespunzator unui nod $X$ are $O(L)$ caractere.

Solutia oficiala foloseste un algoritm de constructie a unui 'automat finit determinist':http://en.wikipedia.org/wiki/Deterministic_finite_state_machine avand complexitate $O(N*L^2^)$. Se va construi trie-ul cuvintelor, apoi, pe baza acestui trie, se va calcula un automat care are un numar de stari egal cu numarul de noduri ale trie-ului. Pentru fiecare stare $X$ si fiecare caracter $c$, se va calcula functia $nextState[X,c]$, reprezentand starea ce corespunde celui mai lung sir care este un subsir al sirului corespunzator starii $X$ concatenat cu caracterul $c$. Pentru starile $X$ ce au fiu in trie corespunzator unui caracter $c$, $nextState[X,c]$ va fi egal cu acest fiu. Pentru celelalte caractere si o stare $X$, vom avea $O(L)$ stari candidate. Mai exact, sa consideram ca $TX$ este tatal nodului $X$ in trie (presupunand ca $X$ nu este radacina trie-ului) si ca avem starile $Q{~0~}, Q{~1~}, .., Q{~P~}$ stari ce corespund sufixelor de lungime $0, 1, .., P$ ale sirului corespunzator nodului $TX$ (acest sir are $P+1$ caractere). Atunci multimea de stari $R{~1~}, .., R{~P+1~}$ avand aceeasi semnificatie pentru nodul $X$ se calculeaza ca fiind $R{~1~}=fiu[Q{~0~},u], R{~2~}=fiu[Q{~1~},u], .., R{~P+1~}=fiu[Q{~P~},u]$, unde $X=fiu[TX,u]$, adica fiul nodului $TX$, ce corespunde caracterului u. La aceasta multime vom adauga pe R{~0~}=radacina trie-ului (ce corespunde sirului vid). $nextState[X,c]$ va fi egal cu sirul de lungime maxima dintre sirurile corespunzatoare nodurilor $fiu[R{~i~},c]$, cu $0 ≤ i ≤ P+1$. Se observa usor ca pentru orice nod $X$ pot exista cel mult $O(L)$ stari candidate, deoarece sirul corespunzator unui nod $X$ are $O(L)$ caractere.

O solutie mai simpla si care ar obtine punctajul maxim consta in folosirea unor functii de hash, ca in algoritmului 'Rabin-Karp':http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm. Aceste functii trebuie sa fie calculabile usor ({$in O(1)$}) atunci cand avem valoarea hash-ului pentru un sir $S$ si dorim sa calculam valoarea pentru sirul $S'$ obtinut prin adaugarea unui caracter la dreapta lui $S$ si inlaturarea unui caracter din stanga lui $S$. Cateva variante de functii de hash ar putea fi urmatoarele:

* scrierea sirurilor ca numere in baza $3$ (intrucat alfabetul consta doar din $3$ litere) => este ideea de mai sus, dar cu $P=3$.
h3. Probleme asemanatoare

* 'Dangerous Pattern / ZJU':http://acm.zju.edu.cn/show_problem.php?pid=2115

h2. Tritzi

h2. 'Tritzi':problema/tritzi
 
h3. Algoritm de complexitate $O(N)$
 
Vom calcula valorile $T[i,j]$, reprezentand numarul de siruri de $i$ tritzi, pentru care ultimul trit are valoarea $j$. $T[1,j] = (1 mod P)$. Pentru $i > 1$, avem:
 
* $T[i, 0] = (T[i-1, 0] + T[i-1, 2]) mod P$
* $T[i, 1] = (T[i-1, 1] + T[i-1, 2]) mod P$
* $T[i, 2] = (T[i-1, 0] + T[i-1, 1] + T[i-1, 2]) mod P$
 
Aplicarea directa a acestor relatii de recurenta conduce la un algoritm liniar, care, insa, nu se incadreaza in limita de timp.
 
h4. Algoritm de complexitate $O(log N)$ - varianta 1
 
Folosind relatiile de recurenta de mai sus, putem construi o matrice $A$ de iteratie si vom privi $T[i]$ ca pe un vector coloana. Avem relatia: $T[i] = A * T[i-1]$. $T[N] = A^N-1^ * T[1]$. $T[1]$ este cunoscut direct, iar $A^N-1^$ se poate calcula in complexitate $O(log N)$, folosind exponentiere logaritmica.
 
h4. Algoritm de complexitate $O(log N)$ - varianta 2
 
Vom calcula o matrice $T[x][i][y]$ = numarul de siruri de tritzi (mod P), de lungime $2^i^$ si pentru care primul trit are valoarea $x$, iar ultimul trit are valoarea $y$. $T[x][0][y]$ se determina direct, iar pentru $i > 0$, $T[x][i][y]$ va fi egal cu o suma din $T[x][i-1][a] * T[b][i-1][y]$, unde $a$ si $b$ sunt doua valori ({$0$}, $1$ sau {$2$}) care pot fi plasate una dupa alta.
 
Apoi vom scrie numarul $N$ ca o suma de puteri ale lui $2$: $N = 2^p1^ + 2^p2^ + ..  2^pK^$. Vom calcula o matrice $U[x][i][y]$ = numarul de siruri de tritzi (mod P) de lungime $2^p1^ + 2^p2^ + .. + 2^pi^$, pentru care primul trit are valoarea $x$ si ultimul trit are valoarea $y$. Avem $U[x][0][y] = T[x][p0][y]$. Pentru $i > 0$, $U[x][i][y]$ este egal cu o suma din $U[x][i-1][a] * T[b][pi][y]$, unde $a$ si $b$ sunt doua valori de tritzi care pot fi plasate una dupa alta. Rezultatul final il vom obtine adunand toate valorile $U[x][K][y]$, unde $K$ este numarul de biti de $1$ din reprezentarea binara a lui $N$.
 
h3.Probleme asemanatoare
 
* 'iepuri / preONI 2005':http://infoarena.ro/problema/iepuri
* 'Nice Patterns Strike Back / SGU':http://acm.sgu.ru/problem.php?contest=0&problem=197
* 'Fibo / .campion 2003':http://campion.edu.ro/problems/3/106/fibo.htm

h2. Regine2