INFOMAN брой 18

/*
Õàêåð

Ïåøî-õàêåðà îáè÷à äà õàêâà îòäàëå÷åíè êîìïþòðè ïðåç telnet. Ïðåç ðúöåòå ìó ñà ìèíàëè êàêâè ëè íå ñúðâúðè è îïåðàöèîííè ñèñòåìè. ђåäíúæ Ïåøî óñïÿë â îáèêíîâåíà ÷àò-ñåñèÿ ïîä ñúâñåì òúï ïðåäëîã äà ïîëó÷è ïàðîëàòà íà íàèâåí ïîòðåáèòåë íà îòäàëå÷åíà ìðåæà. ђúïðîñíàòà ìðåæà áèëà ìíîãî ñòðàííà. Ðàáîòåëà ïîä îïåðàöèîííà ñèñòåìà, ñèëíî íàïîìíÿùà ÄÎÑ. Èìåíàòà íà ôàéëîâåòå ñå ñúñòîÿëè ñàìî îò ãëàâíè ëàòèíñêè áóêâè è öèôðè è èìàëè äúëæèíà äî 20 ñèìâîëà. Îñâåí òîâà Ïåøî îòêðèë, ÷å èìàëà ìíîãî ñòðàííè ïðàâà íà äîñòúï, ïîçâîëÿâàùè èçïúëíåíèå íà íå ïîâå÷å îò 100 êîìàíäè îò ïðîìïòà íà ñåñèÿ. Òàêà ïîíå áèëî çà ïîòðåáèòåëÿ, îò ÷èåòî èìå ñå âêëþ÷âàë. Ïåøî ðàçãëåäàë âíèìàòåëíî ìðåæàòà è ñêîðî îòêðèë, ÷å òÿ å ïúëíî äúðâî è ÷å ïðîöåñîðúò ÷åñòî ñå ïðåòîâàðâà, ïîðàäè êîåòî âñè÷êè, ñ èçêëþ÷åíèå íà àäìèíèñòðàòîðà èìàëè ïðàâî íà îãðàíè÷åí áðîé êîìàíäè. Ïåøî-õàêåðà ìíîãî ñå ïîäðàçíèë îò òîâà. Ïðîó÷èë îùå ìàëêî ìðåæàòà è ñêîðî óñòàíîâèë êîè ñà æèçíåíîâàæíèòå é ôàéëîâå, ñëåä êîåòî åñòåñòâåíî ìó ñå ïîèñêàëî äà ãè òúðíå, òà äà îòúðâå ñâåòà îò äúðâîòî...
Èìàëî îáà÷å ïðîáëåì. Ïåøî öåíÿë òðóäà íà îáèêíîâåíèòå ïîòðåáèòåëè è íèêîãà íå ïîâðåæäàë ôàéëîâåòå èì, êàòî ñè ïîçâîëÿâàë äà ñêàïâà ñàìî ñèñòåìíèòå ôàéëîâå. Çà ñúæàëåíèå âúïðîñíàòà ñèñòåìà áèëà ãîëÿìî äúðâî è íå ïîääúðæàëà äúðâîâèäíà ñòðóêòóðà è äèðåêòîðèèòå. ђñè÷êèòå ôàéëîâå (íå áèëè ìíîãî - íÿêîëêî õèëÿäè) ñå íàìèðàëè â åäíà è ñúùà äèðåêòîðèÿ. Ïåøî ðàçáðàë, ÷å êîìàíäàòà çà èçòðèâàíå å DEL è ÷å îïåðàöèîííàòà ñèñòåìà ïîääúðæà ñòàíäàðòíèòå ñèìâîëè ? è *. Ïúðâèÿò çàìåñòâàë ïðîèçâîëåí ñèìâîë (áóêâà èëè öèôðà), à âòîðèÿò - ïîñëåäîâàòåëíîñò îò 0,1, èëè ïîâå÷å ñèìâîëà. Ñèìâîëúò * ìîæåë äà ñå ïîñòàâÿ ñàìî â êðàÿ íà ìàñêàòà. Ïåøî áèë ìúðçåëèâ ÷îâåê ïúê, ìúðçÿëî ãî äà ïèøå ìíîãî, áèë îãðàíè÷åí îò îïåðàöèîííàòà ñèñòåìà ïî îòíîøåíèå íà áðîÿ ðàçðåøåíè êîìàíäè íà ñåñèÿ, ïúê è ñè ïàäàë ìàíèàê. Ðåøèë äà ïîêàæå êîëêî å óìåí íà àäìèíèñòðàòîðà è äà èçòðèå ôàéëîâåòå ñ ìèíèìàëåí áðîé êîìàíäè DEL. 
Çà öåëòà èçãîòâèë äâà îòäåëíè ñïèñúêà. ђ ïúðâèÿ çàïèñàë èìåíàòà íà âñè÷êè ôàéëîâå ïî åäíî íà ðåä è ãî çàïàçèë ïîä èìåòî FILES.TXT. ђúâ âòîðèÿ çàïèñàë íîìåðàòà íà òåçè ôàéëîâå îò FILES.TXT, êîèòî òðÿáâà äà áúäàò èçòðèòè, êàòî ãè ðàçäåëèë ñ ïîíå åäèí èíòåðâàë èëè çíàê çà íîâ ðåä. Ñëåä òîâà ñåäíàë äà ïèøå ïðîñòà ïðîãðàìêà, êîÿòî äà ìó ïîäãîòâè íóæíèÿ ñêðèïò (ïîñëåäîâàòåëíîñò îò êîìàíäè DEL ïî åäíà íà ðåä) è äà ãî çàïèøå âúâ ôàéëà HACKER.OUT. Ïðîáëåìúò å, ÷å ìàêàð è âåëèê õàêåð, Ïåøî å ìàëêî ñêàðàí ñ àëãîðèòìèòå. Ïîìîãíåòå ìó äà ñè íàïèøå íóæíàòà ïðîãðàìà!

ÏÐÈÌÅÐ:

FILES.TXT
PRESLAV
PRESLI
BRESLAV
BRESLA
PRESLATA
PROST
PARASIT
PARAVAN
PRASKAM
PASCAL

DELETE.TXT
1 3 4 5 6 9

HACKER.OUT
DEL PROST
DEL ?R?S?A*

Ðåøåíèå:
	Çàäà÷àòà ìîæå äà ñå ðàçãëåæäà êàòî îáîáùåíèå íà çàäà÷àòà çà ìèíèìèçàöèÿ íà áóëåâà ôóíêöèÿ è ïî ñïåöèàëíî íà çàäà÷àòà çà íàìèðàíå íà ìèíèìàëíàòà äèçþíêòèâíà íîðìàëíà ôîðìà. Ñòàíäàðòåí ïîäõîä êúì ðåøåíèåòî íà çàäà÷àòà å íàìèðàíå íà ïðîñòèòå èìïëèêàíòè ïî àëãîðèòúìà íà Êóàéí-ÌàêÊëàñêè, ñëåä êîåòî ñå èçáèðà ìèíèìàëíà ÷àñò îò òÿõ, òàêà ÷å äà ïîêðèâàò èçöÿëî åäèíèöèòå íà ôóíêöèÿòà. Ïîñëåäíîòî íà ïðàêòèêà ñå ñâåæäà äî ðåøàâàíå íà çàäà÷à çà ìèíèìàëíè ïîêðèòèÿ. [1]
ёåç äà íàâëèçàìå â èçëèøíè ïîäðîáíîñòè è íåíóæíè ìàòåìàòè÷åñêè ôîðìàëèçìè, ïî-äîëó ùå ñå îïèòàìå äà ñêèöèðàìå èäåÿòà. Çàäà÷àòà çà ìèíèìèçèðàíå íà áóëåâà ôóíêöèÿ å ðàçãëåäàíà ïîäðîáíî îò Ìàíåâ â [1]. Öåëòà å ïîëó÷àâàíå íà çàïèñ íà áóëåâàòà ôóíêöèÿ, ñúäúðæàù ìèíèìàëåí áðîé áóêâè íà ïðîìåíëèâè. Ïàê òàì å ðàçãëåäàí è ÷àñòíèÿò ñëó÷àé íà çàäà÷àòà çà íàìèðàíå íà ìèíèìàëíàòà äèçþíêòèâíà íîðìàëíà ôîðìà. ѐëãîðèòúìúò ïðîòè÷à íà äâå ñòúïêè: íà ïúðâàòà ñòúïêà ñå òúðñÿò ïðîñòèòå èìïëèêàíòè ïî àëãîðèòúìà íà Êóàéí-ÌàêÊëàñêè. Çàïî÷âà ñå îò ñïèñúê íà âñè÷êè äèçþíêòè íà ñúâúðøåíàòà äèçþíêòèâíà ôîðìà. Ñëåä òîâà ñå òúðñÿò âñè÷êè äâîéêè èçìåæäó äèçþíêòèòå, êîèòî ñå îòëè÷àâàò â òî÷íî åäíà ïîçèöèÿ (ïðîìåíëèâà): â åäèíèÿ äèçþíêò ïðîìåíëèâàòà å ñ ÷åðòà, à â äðóãèÿ - áåç. Çà âñÿêà òàêàâà äâîéêà äèçþíêòè ñå ïîëó÷àâà íîâ äèçþíêò, â êîéòî âúïðîñíàòà ïðîìåíëèâà îòïàäà. Òîé ïîêðèâà åäèíèöèòå è íà äâàòà äèçþíêòà, îò êîèòî ñå ïîëó÷àâà. Äèçþíêòèòå, êîèòî ñà ñå êîìáèíèðàëè óñïåøíî ñ ïîíå åäèí äðóã äèçþíêò ñå îòáåëÿçâàò ñ *. Íà ñëåäâàùàòà ñòúïêà ñå îïèòâà àíàëîãè÷íî êîìáèíèðàíî, íî ìåæäó äèçþíêòèòå, ïðîèçëåçëè â ðåçóëòàò íà êîìáèíàöèÿ íà ïðåäõîäíàòà ñòúïêà. Ïðîöåñúò ïðîäúëæàâà äî ïîëó÷àâàíå íà 0 èëè åäíà èìïëèêàíòè. ђñè÷êè íåîòáåëÿçàíè ñ * äèçþíêòè ñà ïðîñòè èìïëèêàíòè íà ôóíêöèÿòà (ò.å. ïðåìàõâàíåòî íà êîÿ äà å áóêâà îò òÿõ âîäè äî ïîëó÷àâàíå íà äèçþíêò, êîéòî íå ïðèíàäëåæè íà ÄÍÔ íà ôóíêöèÿòà). 
Íà âòîðàòà ñòúïêà íà àëãîðèòúìà ñå èçáèðàò ÷àñò îò íåîòáåëÿçàíèòå ñ * äèçþíêòè (òå îáðàçóâàò òàêà íàðå÷åíàòà Ñúêðàòåíà ÄÍÔ), òàêà ÷å äà ïîêðèâàò èçöÿëî ôóíêöèÿòà è ñúùåâðåìåííî áðîÿò íà áóêâèòå â òÿõ äà áúäå ìèíèìàëåí. Çà öåëòà ñå ðåøàâà çàäà÷àòà çà ìèíèìàëíèòå ïîêðèòèÿ, â ðåçóëòàò íà êîåòî ñå íàìèðàò âñè÷êè íåïðèâîäèìè ÄÍÔ íà ôóíêöèÿòà. Èçìåæäó òÿõ ñå èçáèðàò òåçè, êîèòî ñúäúðæàò ìèíèìàëåí áðîé áóêâè íà ïðîìåíëèâè. 

Êàê ñòîÿò íåùàòà â íàøèÿ ñëó÷àé è êàê ãîðíèòå àëãîðèòìè ìîãàò äà ñå èçïîëçâàò çà ðåøàâàíå íà íàøàòà çàäà÷à? Îêàçâà ñå, ÷å èäåÿòà íà àëãîðèòúìà íà Êóàéí-Ìàêëàñêè ñå ïðåíàñÿ ïî÷òè äèðåêòíî. Íà ïúðâàòà ñòúïêà ñå èíèöèàëèçèðàò íÿêîëêî ñïèñúêà:
1) ñïèñúê íà ôàéëîâåòå çà èçòðèâàíå: D;
2) ñïèñúê íà îñòàíàëèòå ôàéëîâå: R;
3) ïðàçåí ñïèñúê C íà êîìáèíàöèèòå ìåæäó åëåìåíòè íà D, íåâëèçàùè â êîíôëèêò ñ òåçè îò R;
4) ïðàçåí ñïèñúê F íà "ïðîñòèòå èìïëèêàíòè".
Íà âñÿêà ñòúïêà íà àëãîðèòúìà ñå êîìáèíèðàò (â íîâ ñïèñúê C) âñè÷êè âúçìîæíè äâîéêè èìåíà íà ôàéëîâå îò D, çà êîèòî ïîëó÷åíàòà â ðåçóëòàò íà êîìáèíàöèÿòà ìàñêà (áóêâè è ñïåöèàëíè çíàöè) íå ïîêðèâà íèòî åäèí ôàéë îò R. Åëåìåíòèòå, êîèòî íå ñà ñå êîìáèíèðàëè ñ íèêîé äðóã, ñëåäâà äà ñå ñ÷èòàò çà "ïðîñòè èìïëèêàíòè" è ïîïàäàò â êðàéíèÿ ñïèñúê F. Îñòàíàëèòå ñå ïîêðèâàò îò ìàñêèòå îò C. Íà ñëåäâàùàòà ñòúïêà D ñå èíèöèàëèçèðà ñ åëåìåíòèòå íà C, C ñå èíèöèàëèçèðà ñ ïðàçíèÿ ñïèñúê è ñå ïðàâè îïèò çà êîìáèíèðàíå ìåæäó ìàñêèòå îò D. Ïðîöåñúò ïðîäúëæàâà äîêàòî ïðè ïîðåäíàòà ñòúïêà â C ïîïàäà ïîíå åäèí åëåìåíò. ђ òîçè ìîìåíò F ùå ñúäúðæà âñè÷êè "ïðîñòè èìïëèêàíòè" íà èçõîäíîòî ìíîæåñòâî îò ôàéëîâå çà èçòðèâàíå. 
Êàê ñòàâà êîìáèíèðàíåòî íà äâîéêà ôàéëîâå â îáùà ìàñêà? ѐëãîðèòúìúò å ïðîñò: Äâàòà íèçà ñå ñêàíèðàò ïîñëåäîâàòåëíî è åäíîâðåìåííî. ѐêî ñúîòâåòíèòå ñèìâîëè ñúâïàäàò, òî ìàñêàòà ùå ñúäúðæà ñúùèÿ ñèìâîë. ђ ïðîòèâåí ñëó÷àé ùå ñúäúðæà ? íà ñúîòâåòíàòà ïîçèöèÿ. ѐêî åäèíèÿò îò ñèìâîëèòå çàâúðøâà íà *, òî è óíèôèöèðàíèÿò íèç ùå çàâúðøâà íà *. ѐêî åäèíèÿò íèç å ïî-äúëúã îò äðóãèÿ, òî ìàñêàòà ùå ñúäúðæà * â êðàÿ ñè. Îñòàâà äà ñå ïðîâåðè äàëè ïîëó÷åíàòà ìàñêà m íå ñå óíèôèöèðà ñ íÿêîé îò ôàéëîâåòå, êîèòî íå áèâà äà ñå èçòðèâàò, â êîéòî ñëó÷àé ñëåäâà äà ñå îòõâúðëè. Ïðîâåðêàòà çà êîíêðåòåí ôàéë f ñòàâà êàòî ñå óíèôèöèðà f ñ m. ѐêî â ðåçóëòàò ñå ïîëó÷è îòíîâî m, òî f ñå ïîêðèâà îò m è ñëåäîâàòåëíî m òðÿáâà äà ñå îòõâúðëè.
Òàêà ïîëó÷àâàìå ñïèñúê îò "ïðîñòè èìïëèêàíòè". Îñòàâà äà èçõâúðëèì íÿêîè îò òÿõ, òàêà ÷å îñòàíàëèòå äà áúäàò ìèíèìàëåí áðîé è äà ïîêðèâàò öÿëîòî ìíîæåñòâî îò èçòðèâàíè ôàéëîâå. Òàçè çàäà÷à å òðóäíî ðåøèìà, ò.å. íÿìà ïîëèíîìèàëíî ðåøåíèå. Ñúùåñòâóâà ëàêîìî ðåøåíèå, ïðè êîåòî ÷îâåê íà âñÿêà ñòúïêà ñå îïèòâà äà ïðèáàâè òàçè ìàñêà, êîÿòî ïîêðèâà ìàêñèìàëåí áðîé íåïîêðèòè ôàéëîâå. [2]
ђ ïðèëîæåíàòà ïðîãðàìà çàäà÷àòà ñå ðåøàâà ïî ìåòîäà íà òúðñåíåòî ñ âðúùàíå íàçàä. Íà âñÿêà ñòúïêà ñå ïðàâè îïèò çà äîáàâÿíå íà ñëåäâàùàòà ìàñêà, íî ñàìî àêî òðèå ïîíå åäèí íåèçòðèò äî ìîìåíòà ôàéë çà èçòðèâàíå. Ñëåä âêëþ÷âàíåòî íà íîâàòà ìàñêà ñå ïðàâè ïðîâåðêà äàëè íÿêîÿ îò ìàñêèòå, âêëþ÷åíè íà ïðåäõîäíèòå ñòúïêè, íÿìà äà ñå îêàæå èçëèøíà. Çàäà÷àòà ìîæå äà ñå ðåøè è ñ ïîòîê.
ѐëãîðèòúìúò ìîæå äà ñå óñêîðè, â íÿêîè ñëó÷àè çíà÷èòåëíî, àêî ïðåäâàðèòåëíî ñå îòñòðàíÿò ÿäðîâèòå ìàñêè (âèæ [1]), ò.å. òåçè, êîèòî åäèíñòâåíè òðèÿò íÿêîé îò ôàéëîâåòå çà èçòðèâàíå.

Ñëåäâà ðåçóëòàò îò èçïúëíåíèåòî íà ïðîãðàìàòà âúðõó ïðèìåðåí âõîä.
Ôàéëîâå:
PRESLAV
PRESLI
BRESLAV
BRESLA
PRESLATA
PROST
PARASIT
PARAVAN
PRASKAM
PASCAL
BORLANDC
BARBADOS
BANICA
PANICA
PERKA
PERKO
PERALNJA
KANDILO
KARAMBOL
KASKADA
KARAMFIL
KROKODIL
KILIM
FROST
LOST
DELETE
PELETI
PELENI
Òðèåì:
1 3 4 5 6 9 10 11 12 15 16 17 19 20 25 27 28
Ðåçóëòàò:
Step 1:
PRESLAV + BRESLAV = ?RESLAV
PRESLAV + BRESLA = ?RESLA*
PRESLAV + PRESLATA = PRESLA?*
PRESLAV + PRASKAM = PR?S?A?
PRESLAV + PERALNJA = P???L??*
BRESLAV + BRESLA = BRESLA*
BRESLAV + PRESLATA = ?RESLA?*
BRESLAV + PRASKAM = ?R?S?A?
BRESLAV + BORLANDC = B??????*
BRESLAV + PERALNJA = ????L??*
BRESLA + PRASKAM = ?R?S?A*
PRESLATA + PRASKAM = PR?S?A?*
PRESLATA + PERALNJA = P???L??A
PROST + PERKA = P????
PROST + PELETI = P???T*
PASCAL + BORLANDC = ????A?*
PASCAL + BARBADOS = ?A??A?*
PASCAL + PERKA = P???A*
PASCAL + KASKADA = ?AS?A?*
PASCAL + LOST = ??S?*
BORLANDC + BARBADOS = B?R?A???
BORLANDC + PERKA = ??R?A*
BORLANDC + PERALNJA = ??R??N??
BORLANDC + KASKADA = ????A??*
BORLANDC + LOST = ?O??*
BARBADOS + KARAMBOL = ?AR???O?
BARBADOS + KASKADA = ?A??AD?*
PERKA + PERKO = PERK?
PERKA + PERALNJA = PER??*
PERKA + KASKADA = ???KA*
PERKA + PELETI = PE???*
PERALNJA + PELETI = PE????*
PELETI + PELENI = PELE?I
Step 2:
?RESLAV + ?RESLA* = ?RESLA*
?RESLAV + PRESLA?* = ?RESLA?*
?RESLAV + PR?S?A? = ?R?S?A?
?RESLAV + P???L??* = ????L??*
?RESLAV + ?R?S?A* = ?R?S?A*
?RESLAV + PR?S?A?* = ?R?S?A?*
PRESLA?* + PR?S?A? = PR?S?A?*
PRESLA?* + P???L??* = P???L??*
B??????* + B?R?A??? = B??????*
P???? + PERK? = P????
????A?* + ?A??A?* = ????A?*
????A?* + P???A* = ????A*
?A??A?* + ?AS?A?* = ?A??A?*
?AS?A?* + ??S?* = ??S?*
B?R?A??? + ??R?A* = ??R?A*
B?R?A??? + ????A??* = ????A??*
PERK? + PER??* = PER??*
PERK? + PE???* = PE???*
PE????* + PELE?I = PE????*
Step 3:
?RESLA* + ?RESLA?* = ?RESLA*
?RESLA* + ?R?S?A? = ?R?S?A*
?RESLA?* + ?R?S?A? = ?R?S?A?*
?RESLA?* + ????L??* = ????L??*
????A?* + ????A* = ????A*
????A?* + ?A??A?* = ????A?*
PER??* + PE???* = PE???*
Step 4:
?RESLA* + ?R?S?A* = ?R?S?A*
????A* + ????A?* = ????A*
Step 5:

File list to minimize now...:
DEL P???T*
DEL ??R??N??
DEL ?O??*
DEL ?AR???O?
DEL B??????*
DEL P????
DEL ??S?*
DEL ????L??*
DEL PE???*
DEL ?R?S?A*
DEL ????A*

You must perform the following delete operations:
DEL P???T*
DEL ??R??N??
DEL ?AR???O?
DEL ??S?*
DEL PE???*
DEL ?R?S?A*
DEL ????A*

	Ïðåäëîæåíàòà ïðîãðàìà íà C++ î÷àêâà êàòî âõîä äâà ôàéëà: åäèí, ñúäúðæàù èìåíàòà íà ôàéëîâåòå, è âòîðè - ñúäúðæàù èíäåêñèòå íà ôàéëîâåòå çà èçòðèâàíå. Ðåçóëòàòúò ñå èçâåæäà íà åêðàíà, êàòî ñå èçâåæäàò è ìåæäèííèòå ðåçóëòàòè îò âñÿêà ñòúïêà íà àëãîðèòúìà íà Êóàéí-ÌàêÊëàñêè.

Ëèòåðàòóðà:
1. Ìàíåâ Êð., "Óâîä â äèñêðåòíàòà ìàòåìàòèêà", Íîâ áúëãàðñêè óíèâåðñèòåò, Ñîôèÿ, 1996.
2. Skiena S., "The algorithm design manual", Springer-Verlag, New York, 1998.
*/

#define MAX 1000
#define MAX_FNAME_LEN 100

#define INPUT_FILE  "files.txt"
#define DELETE_FILE "delete.txt"

// Boolean constants
#define TRUE  1
#define FALSE 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct {
	char *fname;
	int toDel;
} files[MAX];				// List of file names to do NOT delete
unsigned int fcnt;			// Count of file names to do NOT delete

struct {
	char *fname;
	int used;
} del[MAX];					// Strings to delete
unsigned int dcnt;			// Strings to delete count

char *toDel[MAX];			// Strings to delete
unsigned int toDelCnt;

char *unif[MAX*MAX];		// Unified strings
unsigned int ucnt;			// Unified strings count

char *final[MAX];			// Final strings
unsigned int finalCnt = 0;  // Final strings count


void readInputFile() // Get the file names
{
	FILE *fp;
	char s[MAX_FNAME_LEN];
	if ((fp = fopen(INPUT_FILE,"rt")) == NULL) {
		fprintf(stderr,"\nError while trying to open %s for reading!",INPUT_FILE);
		exit(-1);
	}

	fcnt = 0;
	while (!feof(fp)) {
		fscanf(fp,"%s",s);
		files[fcnt].fname = strdup(s);
		files[fcnt++].toDel = FALSE;
	}	

	fclose(fp);
}

void readDeleteFile() // Get the file names
{
	unsigned int i,ind;
	FILE *fp;
	if ((fp = fopen(DELETE_FILE,"rt")) == NULL) {
		fprintf(stderr,"\nError while trying to open %s for reading!",DELETE_FILE);
		exit(-1);
	}

	// Get the files to delete
	for (dcnt = 0; !feof(fp); dcnt++) {
		unsigned int ind;
		fscanf(fp,"%u",&ind);
		files[ind-1].toDel = TRUE;
		del[dcnt].fname = strdup(files[ind-1].fname);
		toDel[dcnt] = strdup(files[ind-1].fname);
		del[dcnt].used = FALSE;
	}
	toDelCnt = dcnt;

	// Remove them from the files list
	for (i = ind = 0; i < fcnt; i++)
		if (!files[i].toDel && i != ind) 
			files[ind++].fname = files[i].fname;
	fcnt = ind;

	fclose(fp);
}

char *unify(char *s1, char *s2, char *result) // Unify two strings
{
	char *res = result;
	if (s1 == NULL || s2 == NULL) return NULL;
	while (*s1 && *s2) {
		if (*s1 == '*' || *s2 == '*') *result++ = '*'; 
		else *result++ = (*s1 == *s2) ? *s1 : '?';
		*s1++; *s2++;
	}

	if (*s1 != *s2 && *(result-1) != '*') *result++ = '*';

	*result = '\0'; 
	return res;
}

void doUnify() 
{
	char s[MAX_FNAME_LEN], s2[MAX_FNAME_LEN];
	unsigned int i,j,k;
	int flag;
	
	ucnt = 0;
	for (i = 0; i < dcnt-1; i++) 
		for (j = i+1; j < dcnt; j++) {
			unify(del[i].fname,del[j].fname,s); // Get the unified code
	
			// Check if it matches a non-delete file name
			for (k = 0, flag = FALSE; k < fcnt; k++)
				if (strcmp(s,unify(files[k].fname,s,s2)) == 0) 
					{ flag = TRUE; break; }

			if (!flag) {
				del[i].used = del[j].used = TRUE;
				// Check if it does exist already
				for (k = 0, flag = FALSE; k < ucnt; k++)
					if (strcmp(s,unif[k]) == 0) { flag = TRUE; break; }
			}

			if (!flag) {
				unif[ucnt++] = strdup(s);
				printf("%s + %s = %s\n",del[i].fname,del[j].fname,s);
			}
		}
}

void getFinals() // Get the finals
{
	for (unsigned int i = 0; i < dcnt; i++)
		if (!del[i].used) 
			final[finalCnt++] = strdup(del[i].fname);
}

void prepareNextStep() // Prepare the next iteration step
{
	unsigned int i;
	// Free the memory allocated by the old file names
	for (i = 0; i < dcnt; i++) free(del[i].fname);
	// Put in the new files
	dcnt = ucnt;
	for (i = 0; i < ucnt; i++) {
		del[i].fname = unif[i];
		del[i].used = FALSE;
	}
}

void printResults() // Output the results
{
	printf("\nFile list to minimize now...:\n");
	for (unsigned int i = 0; i < finalCnt; i++)
		printf("DEL %s\n",final[i]);
}

// ---------------------------------------------------------------------
// ---------------------------------------------------------------------
// ---------------------------------------------------------------------

unsigned int *puiCnt;                  // How much times is the element covered
unsigned char *pa;                     // The spanning matrix
unsigned char *curChoice, *bestChoice; // The family of sets chosen
unsigned int minSets = 100000;         // Minimum sets used
unsigned int elemsCovered = 0;         // Elements covered count

void buildSetCoverMatrix()
{
	unsigned int i,j;
	char s[1000];

	puiCnt = new unsigned int [toDelCnt];
	memset(puiCnt,0,toDelCnt*sizeof(unsigned int));

	curChoice = new unsigned char [finalCnt];
	memset(curChoice,0,finalCnt*sizeof(unsigned char));

	bestChoice = new unsigned char [finalCnt];

	pa = new unsigned char [toDelCnt*finalCnt];
	for (i = 0; i < finalCnt; i++)
		for (j = 0; j < toDelCnt; j++)
			pa[i*toDelCnt+j] = !strcmp(final[i],unify(final[i],toDel[j],s));
}

void cover(unsigned ind) 
{
	unsigned int i,j;
	unsigned char found;

	if (ind == finalCnt) return;

	found = FALSE;
	for (j = 0; j < toDelCnt; j++)
		if (!puiCnt[j] && pa[ind*toDelCnt+j]) { found = TRUE; break; }

	// Try to include the set into the cover family
	if (found) {
		for (i = 0; i < ind && found; i++) {
			// Check if the set is obsolete?
			found = FALSE;
			for (j = 0; j < toDelCnt; j++)
				if (pa[i*toDelCnt+j] && !pa[ind*toDelCnt+j]) { found = TRUE; break; }
		}
		if (found) { // Try to include the set 
			for (j = 0; j < toDelCnt; j++)
				if (pa[ind*toDelCnt+j]) {
					if (!puiCnt[j]) elemsCovered++;
					puiCnt[j]++;
				}
			curChoice[ind] = TRUE;

			// Check if a solution has been found
			if (elemsCovered == toDelCnt) {
				unsigned int cnt = 0;
				for (i = 0; i <= ind; i++) if (curChoice[i]) cnt++;
				if (cnt < minSets) { 
					minSets = cnt; 
					for (i = 0; i <= ind; i++) bestChoice[i] = curChoice[i];
				}
			}
			else cover(ind+1);
			
			curChoice[ind] = FALSE;
			for (j = 0; j < toDelCnt; j++) 
				if (pa[ind*toDelCnt+j]) {
					puiCnt[j]--;
					if (!puiCnt[j]) elemsCovered--;
				}
		}
	}

	// Try to skip the set
	cover(ind+1);
}

// ---------------------------------------------------------------------
// ---------------------------------------------------------------------
// ---------------------------------------------------------------------

void main() {
	unsigned long step = 0;
	readInputFile();
	readDeleteFile();
	do {
		printf("Step %lu:\n",++step);
		doUnify();
		getFinals();
		prepareNextStep();
	} while (ucnt > 0);

	printResults();

	// Solve the minimum set cover
	buildSetCoverMatrix();
	cover(0);

	printf("\nYou must perform the following delete operations:\n");
	for (unsigned int i = 0; i < finalCnt; i++)
		if (bestChoice[i])
			printf("DEL %s\n",final[i]);

	return;
}