In this paper, we present an improved semi-dynamic network decoding strategy by incorporating weighted finite-state transducer (WFST)-based search network. In our approach, a static search network is first optimized by applying WFST algorithms (determinization and minimization) to the composition of a lexicon and a language model. Then the WFST is partitioned into a set of subnetworks according to language model (LM) histories, and transformed into a subnetwork-based search network with exploiting structural differences where a WFST is a Mealy machine and our representation is essentially a Moore machine. This new strategy, which is opposite to our previous approach where each subnetwork depending on a LM history is first constructed and aggregates into a complete network, can let any static network compatible to WFST enjoy the run-time efficiency from the subnetwork-caching operation as well as the static efficiency from the WFST algorithms. The experimental results using Korean read speech dictation task are presented to show its efficiency.