AlgorithmQuestion A dictionary cipher substitutes each word

AlgorithmQuestion

A dictionary cipher substitutes each word in the dictionary by a string according to a codebook. Example codebook can be like below. We have a part of the codebook that allows us to translate some words but are missing the other part. A long cipher-text with n letters is provided. \"jkjkuieuijuuyakjelkjkiekjaueajuseilloppyyaskjirrjkjauieukjkaiejjuyyajjuuyakjel\" Our goal is to split the eipher text to highlight known words and parts that cannot be decoded. For instance, the message, above may above split as follows: \"jkjkuieui in + juuyakjeI + kjkie + kjaue + ajusei + lloppyy +askjirr + jkjauieu + kjkaiejjuyyaj + juuyakjel\" This split yields 6 known codewords (underline) from codebook and 34 characters that are ciphered, i.e., not pint of a known codeword. The cost of such a split is taken to be 6 + 2 * 34 = 74. Formally, we are given a codebook with codewords and a long cipher-text string with ii characters, Our goal is to is to find a minimum cost split that splits the given cipher text into a set of known codewords and ciphered characters so that the cost (define as number of code words + 2 * number of cipher characters) is minimized. Show how a given string can be converted in to a graph whose vertices are the positions in the string and edges encode cost. Show how you can add edges to the graph corresponding to codewords and ciphered characters.

Solution

Now regarding the graph. The value we have calculated in minAnswer can be used to construct the graph.

Just create a graph with labeling the node as indexes of text. Then create an edge between those indexes and put the value over the edge we have calculated in minAnswer. So for example we have edge like 1 to 3, 1 to 4, 2 to 5 etc.

just put value minAnswer[2][5] on edge 2 to 5.

If you have any doubt you can ask me.