#include #define MAXSTAVU 100 #define MAXSLOVO 100 #define MAXTEXT 1000 #define ZNAKU 256 struct { int delka; int zpetna; int prechod[ZNAKU]; } stavy[MAXSTAVU]; int fronta[MAXSTAVU], fpos, fend; struct { char pismeno; int stav; } text [MAXTEXT]; char slovo [MAXSLOVO]; int pocetSlov; int pocetStavu; int delkaTextu; int main (void) { int i; char *p; int stav; int c; gets (slovo); sscanf (slovo, "%d", &pocetSlov); pocetStavu = 1; /* Nulty stav je pocatecni */ /* vytvoreni A-C stromu */ for (i = 0; i < pocetSlov; i++) { gets (slovo); stav = 0; p = slovo; for (p = slovo; *p; p++) if (stavy[stav].prechod[*p]) stav = stavy[stav].prechod[*p]; else { /* pridavame novy stav */ stavy[stav].prechod[*p] = pocetStavu; stav = pocetStavu; pocetStavu ++; } stavy[stav].delka = p - slovo; /* delka slova */ } /* pridame zpetne hrany */ fpos = 0; fend = 0; /* prvni stav je zvlastni pripad */ for (i = 0; i < ZNAKU; i++) if (stavy[0].prechod[i]) fronta[fend++] = stavy[0].prechod[i]; while (fpos < fend) { stav = fronta[fpos++]; for (i = 0; i < ZNAKU; i++) if (stavy[stav].prechod[i]) { int zpetna = stavy[stav].zpetna; int novyStav = stavy[stav].prechod[i]; while (!stavy[zpetna].prechod[i] && zpetna ) zpetna = stavy[zpetna].zpetna; stavy[novyStav].zpetna = stavy[zpetna].prechod[i]; if (stavy[novyStav].delka < stavy[stavy[zpetna].prechod[i]].delka) stavy[novyStav].delka = stavy[stavy[zpetna].prechod[i]].delka; fronta[fend++] = novyStav; } } /* a ted vlastni prace */ stav = 0; delkaTextu = 1; text[0].stav = stav; while ((c = getchar ()) != '\n') { while (stav && !stavy[stav].prechod[c]) stav = stavy[stav].zpetna; stav = stavy[stav].prechod[c]; if (stavy[stav].delka > 0) { /* odstran slovo a obnov stav */ delkaTextu -= stavy[stav].delka - 1; stav = text[delkaTextu - 1].stav; } else { text[delkaTextu].stav = stav; text[delkaTextu].pismeno = (char) c; delkaTextu ++; } } for (i = 1; i < delkaTextu; i++) putchar (text[i].pismeno); putchar ('\n'); return 0; }