#include #include #define MAX_WORDS 100 //maximální počet slov ve slovníku #define MAX_WORD_LEN 100 //maximální délka slova #define MAX_DICT_SIZE 1000 //maximální velikost slovníku #define MAX_NUM_LEN 100 //maximální délka telefonního čísla const char conv[26]={'1','1','1', '2','2', '3','3','3', '4','4', //konvertovací tabulka '5','5','5', '6','6', '7','7','7', '8','8', '9','9','9', '0','0','0'}; char dict[MAX_WORDS][MAX_WORD_LEN]; //slovník typedef struct _TRIE //struktura trie { int succ[10]; //potomci int word; //ukazatel do slovníku nebo 0 } TRIE,*PTRIE; int n,w; //počet čísel, počet slov TRIE trie[MAX_DICT_SIZE]; //trie jako pole vrcholů int trie_count; //počet vrcholů trie int word_count[MAX_NUM_LEN]; //počet slov na dosažení cisla int word_idxs[MAX_NUM_LEN]; //indexy slov ve větě void trie_add(char *s,int idx) //přidá číselný řetězec idx-tého slova do trie { PTRIE t=&trie[0]; //začneme v kořeni trie int len=strlen(s); //délka řetězce for (int i=0;isucc[num]; //index potomka v trii if (!next) //existuje potomek? { trie_count++; //pokud není potomek, vytvoříme ho t->succ[num]=trie_count; //označ potomka next=trie_count; //půjdeme do nového vrcholu } t=&trie[next]; //zanoření o level níž if (i==len-1) t->word=idx; //jsme již na konci slova } return; } int make_sentence(char *numstr) /*utvoří větu pro telefonní číslo do word_count, word_indxs vrací nulu, pokud větu pro dané číslo nelze stvořit*/ { int len=strlen(numstr); //počet cifer telefonního čísla for (int i=0;i<=len;i++) word_count[i]=0; //inicializujeme na 0 = nedosazeno for (int i=-1;isucc[num]; //index potomka v trii if (!next) break; //pokud není potomek, končíme průchod t=&trie[next]; //zanořme se do potomka if (t->word && (!word_count[j])) //končí zde slovo a nebyla tato pozice ještě dosazená? { word_count[j]=wc+1; //zapiš nový počet slov word_idxs[j]=t->word; //index slova ve slovníku } } } return (word_count[len-1]); } int main(int argc,char **argv) { scanf("%d",&w); //načteme slova do slovníku for (int i=1;i<=w;i++) scanf("%s",dict[i]); for (int i=1;i<=w;i++) //zkonvertujeme slova do číselné podoby { char wordnum[MAX_WORD_LEN]; //číselný řetězec int len=strlen(dict[i]); //délka slova for (int j=0;j0) //pro celé telefonní číslo { int idx=word_idxs[numlen-1]; //index slova ve slovníku int len=strlen(dict[idx]); //délka slova ve slovníku j-=len; //posuneme se o délku slova vlevo strncpy(&sentence[j],dict[idx],len); //zkopírujeme slovo if (--j) sentence[j]=' '; //uděláme mezeru mezi slovy numlen-=len; //posuneme se na další slovo } printf("%s -> %s\n",numstr,sentence); //vypíšeme větu } else printf("%s nelze složit\n",numstr); } return 0; }