you must write a method called permu (KMP search algorithm is not allowed), which accepts shortStr (and any other needed parameters; i.e. start index and end index) and generates ALL possible permutation of that string. For each possible permutation value, the method should find out (possibly by calling another method), whether that permutation value is a substring of longStr. Your code must show all permutations and for each of them should indicate whether or not this value exists in longStr.

For example; given longStr as hhhlajkjgabckkkkcbakkdfjknbbca,and shortStr as abc, the method should show display something like:

abc

Found one match: abc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 9 acb

bac

bca

Found one match: bca is in hhhlajkjgabckkkkcbakkdfjknbbca at location 27 cba

Found one match: cba is in hhhlajkjgabckkkkcbakkdfjknbbca at location 16 cab

Given shortStr as ckkk, the method should show display something like:

ckkk

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11

kckk

kckk

kkck

kkkc

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkkc

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck

kkck

kkkc

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kckk

kckk

kkck

kkkc

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkkc

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck

kkkc

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck

kckk

kckk

Note: While our interest is to find if any occurrence of a permutation value exists in longStr (and not all of them; for instance, if abc exists twice in longStr, it is sufficient for the algorithm to find only the first occurrence), you should observe the output carefully, since the characters of shortStr may not be unique, as in the second run!

You will need to run the program multiple times. With each run, you will need to provide a shortStr with an incremented length of 5. That is, you need to run with shortStr of 5 characters, 10 characters, 15 characters, etc. for up to length of 200 characters (or higher value if required for your timing measurement) and measure the corresponding run time for each run. You can use Javas built-in time function for finding the execution time. In each run, you need to provide a longStr that is longer in length than shortStr. The contents of the strings are not important; however, your values should show that you program work correctly. You should redirect the output of each program to an out.txt file. You should write about your observations on timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled executables, and the text files.

Briefly explain what is the complexity of your algorithm. More specifically, is your solution has acceptable complexity; is it scalable enough; etc. If not, what are the reasons behind that?

JAVA LANGUAGE

In your first version, you must write method called permu, which accepts shortStr (and any other needed parameters, i.e. start index and end index) and generates ALL possible permutation of that string. For each possible permutation value, the method should find out (possibly by calling another method), whether that permutation value is a substring of longStr. Your code must show all permutations and for each of them should indicate whether or not this value exists in longStr. For example; given longStr as "hhhlajkjgabckkkkcbakkdfjknbbca" and shortStr as "abc", the method should show display something like: abc Found one match: abc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 9 acb bac bca Found one match: bca is in hhhlajkjgabckkkkcbakkdfjknbbca at location 27 cba Found one match: cba is in hhhlajkjgabckkkkcbakkdfjknbbca at location 16 cab Given shortStr as "ckkk", the method should show display something like: ckkk Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 kckk kckk kkck kkkc Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkkc Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck kkck kkkc Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kckk kckk kkck kkkc Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkkc Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck kkkc Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck kckk kckk Note: While our interest is to find if any occurrence of a permutation value exists in longStr and not all of them; for instance, if abc exists twice in longStr, it is sufficient for the algorithm to find only the first occurrence), you should observe the output carefully, since the characters of shortStr may not be unique, as in the second run! You will need to run the program multiple times. With each run, you will need to provide a shortStr with an incremented length of 5. That is, you need to run with shortStr of 5 characters, 10 characters, 15 characters, etc. for up to length of 200 characters (or higher value if required for your timing measurement) and measure the corresponding run time for each run. You can use Java's built-in time function for finding the execution time. In each run, you need to provide a longStr that is longer in length than shortStr. The contents of the strings are not important; however, your values should show that you program work correctly. You should redirect the output of each program to an out.txt file. You should write about your observations on timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled executables, and the text files. Briefly explain what is the complexity of your algorithm. More specifically, is your solution has acceptable complexity; is it scalable enough; etc. If not, what are the reasons behind that