Code

/* ***************************************************
 * Devon Knudsen
 * Last Updated - 3/16/19
 *
 *
 *************************************************** */

import java.io.*;
import java.time.*;
import java.util.*;

public class Main {
    private static boolean DEBUG = true;

    public static void main(String args[]) throws java.io.IOException {
        DoublyLinkedList<String> text1 = new DoublyLinkedList<>();
        DoublyLinkedList<String> text2 = new DoublyLinkedList<>();
        DoublyLinkedList<String> pattern = new DoublyLinkedList<>();

        Scanner inFile1 = new Scanner(new File("input1.txt"));
        charsToList(fileScan(inFile1), text1);

        Scanner inFile2 = new Scanner(new File("input2.txt"));
        charsToList(fileScan(inFile2), text2);

        if (DEBUG) {
            System.out.println("list 1 = " + text1);
            System.out.println("list 2 = " + text2);
        }

        //Ask the user for the pattern they are looking for and convert it into a linked tex
        Scanner input = new Scanner(System.in);
        System.out.print("Enter the pattern you are searching for: ");
        String[] searchFor = input.nextLine().split("");
        charsToList(searchFor, pattern);

        if (DEBUG) {
            System.out.println("pattern = " + pattern);
        }

        System.out.println(kmp(pattern, text1));
        System.out.println(bruteForce(pattern, text1));
    }

    // function to convert the chars from a read file into a string array
    private static String[] fileScan(Scanner inFile) {
        String fileString = "";
        while (inFile.hasNext())
            fileString += inFile.nextLine();

        String[] chars = fileString.split("");

        inFile.close();

        return chars;
    }

    // function to convert a string array into a linked tex with nodes holding only one char
    private static void charsToList(String[] chars, DoublyLinkedList<String> tex) {
        for (String c : chars)
            tex.InsertAfter(c.toLowerCase());
    }

    /*
    Brute Force algorithm for pattern matching
    (I got some help from the book for this portion of the code)
     */
    private static DoublyLinkedList<Integer> bruteForce(DoublyLinkedList<String> pat, DoublyLinkedList<String> tex) {

        int numMatches = 0;

        // stopwatch starts
        Instant start = Instant.now();

        DoublyLinkedList<Integer> matchAt = new DoublyLinkedList<>();

        // t goes up to the last index that is able to start the pattern which is being searched for
        for(int t = 0; t  < tex.GetSize() - pat.GetSize(); t++) {

            // j = index in pattern
            int p = 0;

            tex.SetPos(t);
            pat.First();

            // if characters matching pattern are found
            while (p < pat.GetSize() && tex.GetValue().equals(pat.GetValue())) {
                p++;
                pat.Next();
                tex.Next();
            }

            // if the end of the pattern is reached
            if (p == pat.GetSize()) {
                matchAt.InsertAfter(t);

                if (DEBUG)
                    numMatches++;
            }
        }

        // stopwatch stops
        Instant finish = Instant.now();

        long timeElapsed = Duration.between(start, finish).toMillis();
        System.out.println(tellTime(timeElapsed, "Brute Force"));

        if(DEBUG)
            System.out.println("Num of matches: " + numMatches);

        if (!matchAt.IsEmpty())
            return matchAt;
        else
            return null;
    }

    /*
    Boyer-Moore algorithm for pattern matching
    (I got some help from the book for this portion of the code)
     */
    //private static DoublyLinkedList<Integer> bm(DoublyLinkedList<String> pat, DoublyLinkedList<String> tex) {
    //}

    /*
    KMP algorithm for pattern matching
    (I got some help from the book for this portion of the code)
     */
    private static DoublyLinkedList<Integer> kmp(DoublyLinkedList<String> pat, DoublyLinkedList<String> tex) {

        int numMatches = 0;


        DoublyLinkedList<Integer> matchAt = new DoublyLinkedList<>();
        if (pat.GetSize() == 0) {
            return null;
        }
        int[] fails = failureFun(pat);

        // stopwatch starts
        Instant start = Instant.now();

        // t = index in text
        // p = index in patten
        int p = 0;
        for(int t = 0; t < tex.GetSize() - pat.GetSize(); t++) {
            tex.SetPos(t);
            pat.SetPos(p);
            if (tex.GetValue().equals(pat.GetValue())) {

                // if the entire pattern is found within the text
                if (p == pat.GetSize() - 1) {
                    matchAt.InsertAfter(t - p);

                    if(DEBUG)
                        numMatches++;

                    t = t - p;
                    p = 0;
                }
                else {
                    p++;
                }
            }

            // the "shifting" of the pattern
            else if (p > 0) {
                //if (fails[p - 1] == 0)
                   // p = 0;
               // else
                    p = fails[p - 1];
            }
        }

        // stopwatch stops
        Instant finish = Instant.now();

        long timeElapsed = Duration.between(start, finish).toMillis();
        System.out.println(tellTime(timeElapsed, "KMP"));

        if(DEBUG)
            System.out.println("Num of matches: " + numMatches);

        if (!matchAt.IsEmpty())
            return matchAt;
        else
            return null;
    }

    /*
    Failure Function needed for the KMP algorithm
    (I got some help from the book for this portion of the code)
     */
    private static int[] failureFun(DoublyLinkedList<String> pat) {
        int[] failure = new int[pat.GetSize()];
        int f = 1;
        int p = 0;
        while(f < pat.GetSize()) {
            pat.SetPos(f);
            String x = pat.GetValue();
            pat.SetPos(p);
            String y = pat.GetValue();
            if (x.equals(y)) {
                failure[f] = p + 1;
                f++;
                p++;
            }
            else if (p > 0)
                p = failure[p - 1];
            else
                f++;
        }

        return failure;
    }

    // function to display the elapsed time of each search algorithm
    private static String tellTime(long tE, String searchType){
        return "Search type: " + searchType + ". Elapsed Time: " + tE + " milliseconds.";
    }
}