Many encryption systems have been developed over the years to keep messages secret. One of the oldest is the simple substitution cipher. In this scheme, each letter in the original plaintext message is consistently replaced by a letter to produce the ciphertext message (e.g., every E is replaced by K). To be reversible, different plaintext letters are not replaced by the same ciphertext letter (e.g., if every E is replaced by K, no other letter will also be replaced by K). It is allowable for a letter to be replaced by itself (e.g., every H is replaced by H). If the sender and receiver have agreed on the substitution scheme (the key), the receiver can easily decrypt the encrypted message. As an example, suppose the key is this:

	ABCDEFGHIJKLMNOPQRSTUVWXYZ   plaintext letters
	NRWZKXCHFBOIMTGVJLYADEPQSU   corresponding ciphertext letters

Then the plaintext message ATTACK AT DAWN would be encrypted as NAANWO NA ZNPT.

Simple substitution ciphers are very insecure; their cryptanalysis (recovering the plaintext message from the ciphertext message without knowing the key) is not difficult. It’s even easier if the cryptanalyst can use a known plaintext attack, one in which there is a word or phrase that is known (or strongly suspected) to occur in the message that was encrypted. This known word or phrase is a crib.

For this project, you will write a function that will take a set of ciphertext messages, all encrypted with the same key, and a crib that occurs in one of the messages. The output will be the set of ciphertext messages, with plaintext letters substituted for ciphertext letters to the extent that they can be determined from the crib. As an example, suppose there are three ciphertext messages:

	Tftdn lxwdqkoft lhgzztr of Ltezgk zvtfzn-ltctf.
	O ziofa zit Zktqlxkt gy Doeiossofrq ol wxkotr lgdtvitkt of dn wqeanqkr.
	Ror ngx itqk ziqz Sgktzzq ol ugofu gxz vozi Dqkexl?
	el 31 ol eiqsstfuofu!

and the crib is treasure of michillinda. The only ciphertext fragment that could possibly be an encryption of the crib (because it’s the only phrase that has words of the right length with the right pattern of repeated letters) is zktqlxkt gy doeiossofrq. That implies that ciphertext z corresponds to plaintext t, k decrypts to r, etc. Your program would output

	ENEMn SUwMARINE ShOTTED IN SECTOR TvENTn-SEcEN.
	I THINa THE TREASURE OF MICHILLINDA IS wURIED SOMEvHERE IN Mn wACanARD.
	DID nOU HEAR THAT LORETTA IS uOINu OUT vITH MARCUS?
	CS 31 IS CHALLENuINu!

The case of letters in ciphertext and the crib is irrelevant. (Notice, for example, that Zktqlxkt matched treasure; the fact that Z is upper case and t is lower case is irrelevant.) However, when you output the (partially) decrypted messages, all plaintext letters must be written in upper case, while remaining ciphertext letters that could not be determined from the crib must be written in lower case. All non-letter characters (punctuation, digits, blanks, newlines, etc.) must be written unchanged.

The function you implement to do this must have the following prototype:

	bool decrypt(const char ciphertext[], const char crib[]);

The parameter ciphertext is a single C string with all the encrypted messages, separated by newline characters. (There may or may not be a newline character after the last message.) For example, a caller who wanted to decrypt the two messages

	Naanwo na znpt
	Wjawjna!

could pass as the first argument "Naanwo na znptnWjawjna!" or "Naanwo na znptnWjawjna!n". You may assume (and thus don’t have to check) that the ciphertext will contain no more than 50 newline characters, and that no message within the ciphertext will be longer than 80 characters (not counting the newline at the end of the message). In other words, there will never be more than 80 characters between two newlines in the ciphertext. It is possible that a message has no words (e.g., is empty, or has digits and spaces but no letters).

The parameter crib is a C string that denotes the crib, the sequence of one or more words that appear consecutively in order in at least one of the ciphertext messages. (A word is a sequence of one or more letters.) One or more blanks separate words in the crib; non-letter characters in crib are to be treated as if they were blanks. Thus, the crib "D-Day is June 6, 1944" should be treated the same as "d day is june", as indicating the sequence consisting of those four words. You must not assume any particular limit to the possible length of the crib string argument that is passed to the function.

If the crib string has no words, or if no ciphertext fragment in any message could possibly be an encryption of the crib, the decrypt function returns false without writing anything to cout. Otherwise, it writes to cout the (partially) decrypted messages as described above and returns true. The decrypt function must not cause any other output to be written to cout. If more than one ciphertext fragment is a possible encryption of the crib, then choose any one of those matching fragments as the match for the crib. For example, if the ciphertext string were "Rzy pkr" and the crib were "dog", then the output would be exactly one of DOG pkD or Gzy DOG, your choice.

A crib word must match an entire ciphertext word. The crib word "aba" matches "cdc" in "cdc ef", but not in "cdcef" or "efcdc". A match for the crib does not span multiple messages. For example, if the ciphertext string were "bwra wmwtnqeirtk spstn", and the crib were "alan turing", the "wmwt" from the first message and the "qeirtk" from the second are not considered a match for the crib.

A word is a sequence of letters only, so the crib "dog" would not match anything in the ciphertext "ew'q p-aj", but the crib "he" could match either ew or aj in that ciphertext. As another example, the crib "s cloak and" matches something in the ciphertext "Kpio't dmpbl-boe-ebhhfs opwfm"; the partially decrypted plaintext would be written as "kOiN'S CLOAK-AND-DAhhfs NOwfL".

All the preceding rules imply that all of these crib strings should be treated the same way:

	"D-Day is June 6, 1944"
	"   d???dAy---      ---iS    JunE !!  "
	"d day is june"

and would match something in the ciphertext string

	"DhaiiA, zyxZYXzyx--A aBc    dE## $$fGhi6437 wvuWVUwvunn8 9n"

causing the partially decrypted plaintext of that string to be written as

	"INDEED, zyxzyxzyx--D DAY    IS## $$JUNE6437 wvuwvuwvunn8 9n"

Your decrypt function and any functions you write that it calls must not use any std::string objects. If you need to use a string, you must use a C string. (Although the program you turn in must not use any C++ strings, only C strings, you might want to consider this development strategy: Ignore this restriction at first, and develop a working solution that uses C++ strings. After you’ve ironed out the issues in writing the decryptor, save a backup, and then convert your using C++ strings to using C strings instead. This approach helps you avoid confusing the mistakes in your use of C strings with the mistakes in your decryption algorithm, so makes debugging easier.)

(Note: Some algorithms that you might consider for your decrypt function may appear at first to require that you assume a limit on the length of the crib string. We prohibited that. But we gave you permission to assume that the maximum length of any message within the ciphertext string is 80, so you know that a crib string that could possibly match only messages longer than 80 characters could not possibly match any of the ciphertext messages; for crib strings like that, you can return false without any further analysis. Thus, if you think about it a little, you can determine maximum limits for any auxiliary arrays and C strings you might want your decrypt function to create.)

The decrypt function is the only function you are required to write. You may write additional functions as part of your solution if you wish. While we won’t test those additional functions separately, their use may help you structure your program more readably. Of course, to test all your functions, you’ll want to write a main routine that calls your decrypt function. During the course of developing your solution, you might change that main routine many times. As long as your main routine compiles correctly when you turn in your solution, it doesn’t matter what it does, since we will rename it to something harmless and never call it (because we will supply our own main routine to throroughly test your decrypt function).

Your decrypt function and any functions it calls must not cause anything to be read from cin. They must not cause anything to be written to cout other than the (partially) decrypted messages required by this spec. If you want these functions to write things out for debugging purposes, write to cerr instead of cout. When we test your program, we will cause everything written to cerr to be discarded instead — we will never see that output, so you may leave those debugging output statements in your program if you wish.

The correctness of your program must not depend on undefined program behavior. Your program could not, for example, assume anything about t‘s value, or even whether or not the program crashes:

	int main()
	{
	    char t[6];
	    strcpy(t, "Enigma");  // too long: 7 chars including ''
	    …

Here’s an example of a main routine that performs some simple tests of the decrypt function:

	void runtest(const char ciphertext[], const char crib[])
	{
	    cout << "====== " << crib << endl;
	    bool result = decrypt(ciphertext, crib);
	    cout << "Return value: " << result << endl;
	}

	int main()
	{
	    cout.setf(ios::boolalpha); // output bools as "true"https://www.sweetstudy.com/"false"

	    runtest("Hirdd ejsy zu drvtry od.nO'z fodvtrry.n", "my secret");
	    runtest("Hirdd ejsy zu drvtry od.nO'z fodvtrry.n", "shadow");
	}

The output of running the program with this main routine would be

	====== my secret
	hiESS ejsT MY SECRET oS.
	o'M foSCREET.
	Return value: true
	====== shadow
	Return value: false

What you will turn in for this assignment is a zip file containing these two files and nothing more:

1. A text file named decrypt.cpp that contains the source code for your C++ program. Your source code should have helpful comments that tell the purpose of your data structures and program segments, and explain any tricky code.

2. A file named report.doc or report.docx (in Microsoft Word format), or report.txt(an ordinary text file) that contains:
   1. A brief description of notable obstacles you overcame.
   2. A description of the design of your program. You should use pseudocode in this description where it clarifies the presentation.
   3. A list of the kinds of test data that could be used to thoroughly test the function, along with the actual data itself. You must note which test cases your program does not handle correctly. (This could happen if you didn’t have time to write a complete solution, or if you ran out of time while still debugging a supposedly complete solution.)

By Monday, May 18, there will be links on the class webpage that will enable you to turn in your zip file electronically. Turn in the file by the due time above. Give yourself enough time to be sure you can turn something in, because we will not accept excuses like “My network connection at home was down, and I didn’t have a way to copy my files and bring them to a SEASnet machine.” There’s a lot to be said for turning in a preliminary version of your program and report early (You can always overwrite it with a later submission). That way you have something submitted in case there’s a problem later. Notice that most of the test data portion of your report can be written from the requirements in this specification, before you even start designing your program.