Vlastně si dodneška nejsem jistý, že jsem AC pochopil až na dno.
Krátký test: Mějme úlohu o cenzorech, o které se už Anička zmiňovala: je dán text a seznam zakázaných slov (podřetězců), chceme vystříhnout všechna zakázaná slova (čímž mohou vzniknout nová zakázaná slova a tak dále). Je jasné, jak udělat lineární řešení, které si bude pamatovat v zásobníku stavy automatu, kterými prošlo? Opravdu? Už? A je teď jasné, proč doopravdy lineární není? :-)
Krátký test: Mějme úlohu o cenzorech, o které se už Anička zmiňovala: je dán text a seznam zakázaných slov (podřetězců), chceme vystříhnout všechna zakázaná slova (čímž mohou vzniknout nová zakázaná slova a tak dále). Je jasné, jak udělat lineární řešení, které si bude pamatovat v zásobníku stavy automatu, kterými prošlo? Opravdu? Už? A je teď jasné, proč doopravdy lineární není? :-)