Úkolem je realizovat část programu (funkci), která umožní analyzovat strukturu genomu a vyhledávat v něm shodné úseky.

V tomto domácím úkolu nebudete implementovat celý program. Budete implementovat pouze jeho část -- jednu funkci se zadaným rozhraním. Funkce má specifikované vstupní parametry a způsob chování. Bude testována tak, že bude vložena do testovacího prostředí (námi vytvořeného programu), odkud bude volaná. Podle návratových hodnot funkce bude vyhodnoceno, zda Vaše implementace funkce je správná.

Konkrétně je Vaším úkolem implementovat funkci, která bude vyhledávat nejdelší společný podřetězec. Vstupem funkce jsou dva řetězce (zde konkrétně dva DNA řetězce, které např. kódují části genomu různých živých organismů). Úkolem funkce je nalézt v těchto řetězcích nejdelší společný úsek a ten vrátit jako nalezený nejdelší společný podřetězec. Pokud existuje více různých společných podřetězců stejné délky, pak je funkce vrátí všechny. Příklady:
s1                s2                nejdelší společný podřetězec (podřetězce)
ATTTCG            GTTCCA            TTC
ATTTATTTA         GTTTCTTTG         TTT
ATTTGTTTA         GTTTATTTG         GTTTA, ATTTG

Požadovaná funkce má rozhraní:
char ** LCS ( char * s1, char * s2 );
s1 a s2 jsou ASCII řetězce (ukazatele na jejich počátek), ve standardní C konvenci (binární nulou ukončené). Řetězce se mohou skládat pouze ze čtyř znaků: A, T, C a G.
Návratová hodnota je dynamicky alokované pole obsahující všechny různé nalezené nejdelší společné podřetězce. Pokud mají vstupní řetězce více společných podřetězců stejné maximální délky, pak budou do výstupu uložené všechny (řetězce GTTTA a ATTTG z ukázky). Naopak, pokud se ten samý společný podřetězec vyskytne vícekrát, je uložen pouze jednou (řetězec TTT v ukázce). Funkce zajistí, že v poli za posledním nalezeným společným podřetězcem bude uložena hodnota NULL. Pořadí řetězců v poli není důležité.
Pokud řetězce nemají žádný společný podřetězec (přesněji - pokud nejdelší společný podřetězec má délku 0 znaků), pak funkce nealokuje pole řetězců, ale rovnou vrátí NULL.
Pokud je na vstupu neplatný řetězec (obsahuje jiné znaky než A, T, C, nebo G), pak funkce rovněž vrátí hodnotu NULL.
Funkce musí návratovou hodnotu alokovat dynamicky. Alokovat je potřeba jednak vracené pole ukazatelů na řetězce a dále i paměť pro uložení vlastních řetězců. Alokaci proveďte funkcí malloc. Testovací prostředí si uložené hodnoty přečte, zkontroluje a paměť uvolní (jednak každý řetězec v poli a nakonec i pole ukazatelů). Za uvolnění ostatních paměťových bloků (které používáte v průběhu výpočtu funkce LCS) jste zodpovědní Vy.

Vaše implementace bude testovaná v prostředí s omezenou velikostí paměti a s limitem na dobu běhu. Limity jsou nastaveny tak, že naivní algoritmus (viz níže) uspěje v základních testech, ale ne již v testech bonusových. První bonus lze získat za rychlejší algoritmus založený na principu dynamického programování (viz níže). Druhý bonus lze získat za zrychlený algoritmus, který navíc bude minimalizovat své paměťové nároky.

Odevzdávejte soubor se zdrojovým kódem, který obsahuje Vaši funkci LCS a případně další Vaše podpůrné funkce, které z funkce LCS voláte. Do souboru nezačleňujte vkládání hlavičkových souborů, funkci main ani další nepotřebné funkce. Pokud je do souboru vložíte, riskujete, že se nepodaří program správně zkompilovat. Abyste nemuseli před odevzdáním opakovaně pracně vykopírovávat Vaší implementaci, využijte preprocesoru a makra __PROGTEST__:
#ifndef __PROGTEST__
#include <stdio.h>
#include <stdlib.h>
...
#endif /* __PROGTEST__ */

char ** LCS ( char * s1, char * s2 )
 {
   /* Vase implementace */
 }

#ifndef __PROGTEST__
int main ( int argc, char * argv [] )
 {
   /* testy Vasi implementace LCS () */
   ...
 }
#endif /* __PROGTEST__ */
Ukázka použití funkce:

/* res = LCS ( "ATAT", "TATA" );
 *
 * res[0] = "TAT"
 * res[1] = "ATA"
 * res[2] = NULL
 */

/* res = LCS ( "AATCG", "CGGCGA" );
 *
 * res[0] = "CG"
 * res[1] = NULL
 */

/* res = LCS ( "AAAATCCGCGCGCCACGCT", "ACGCTCAAAATTTTTGCGCG" );
 *
 * res[0] = "ACGCT"
 * res[1] = "AAAAT"
 * res[2] = "GCGCG"
 * res[3] = NULL
 */

/* res = LCS ( "AAAAAATTTTTTTCCCCCCGGGGGGAAAAAA", "ATCGA" );
 *
 * res[0] = "AT"
 * res[1] = "TC"
 * res[2] = "CG"
 * res[3] = "GA"
 * res[4] = NULL
 */

/* res = LCS ( "AAAAAAAAA", "TTTTTT" );
 *
 * res = NULL
 */

/* res = LCS ( "AAA", "AAAA " );
 *
 * res = NULL
 */
Nápověda:
Naivní algoritmus prostě zkusí pro všechny možné pozice v prvním a všechny možné pozice ve druhém řetězci porovnat, zda se na nich nenachází hledaný společný podřetězec. Pokud dojde ke shodě, určí jeho délku (a případně jej přidá k výstupu). V nejhorším případě provede kubický počet porovnání. Rozumná implementace naivního algoritmu uspěje v základních testech, neuspěje časově v testech bonusových.
Vylepšená verze využívá 2D matici, do které si ukládá nalezené shody znaků. Provádí tedy kvadratický počet porovnání, má tedy šanci pracovat rychleji než naivní algoritmus. Popis algoritmu najdete např. na Wikipedii pod heslem "Longest common substring", podkapitola "dynamické programování".
Vylepšený algoritmus projde prvním bonusovým testem, ale neprojde druhým. V základní implementaci má totiž velké paměťové nároky. Druhým bonusovým testem program projde pokud paměťové nároky snížíte. Neukládejte celou 2D matici, ale pouze relevantní části z ní. Inspiraci najdete na Wikipedii pod heslem "Longest common subsequence".