code

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

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.System.nanoTime;

public class Main {
    private static boolean DEBUG = false;

    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(bruteForce(pattern, text1));
        System.out.println(kmp(pattern, text1));
        System.out.println(bm(pattern, text1));

        if (DEBUG)
            for (int i = 0; i < text2.GetSize(); i++) {
                text2.SetPos(i);
                System.out.println(i + ":" + text2.GetValue());
            }
    }

    // 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) {

        // stopwatch starts
        long start = nanoTime();

        int numMatches = 0;

        int n = tex.GetSize();
        int m = pat.GetSize();

        if (m == 0)
            return null;

        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 <= n - m; t++) {

            // p = index in pattern
            int p = 0;
            tex.SetPos(t);
            pat.First();

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

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

                if (DEBUG)
                    numMatches++;

            }
        }

        // stopwatch starts
        long finish = nanoTime();

        long timeElapsed = finish - start;
        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
    Got help from geeksforgeeks on this one:
        URL -> https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/
     */
    private static DoublyLinkedList<Integer> bm(DoublyLinkedList<String> pat, DoublyLinkedList<String> tex) {

        // stopwatch starts
        long start = nanoTime();

        int numMatches = 0;

        int n = tex.GetSize();
        int m = pat.GetSize();

        if (m == 0)
            return null;

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

        int s = 0;
        while (s <= n - m) {
            int j = m - 1;
            int k = 0;

            pat.SetPos(j);
            tex.SetPos(s + j);

            while (j >= 0 && pat.GetValue().equals(tex.GetValue())) {
                pat.Prev();
                tex.Prev();
                j--;
                k++;
            }

            if (j < 0) {
                matchAt.InsertAfter(s);

                if (DEBUG)
                    numMatches++;

                tex.SetPos(s + m);
                int gek = backCheckBC(pat, tex, "true");
                if (pat.GetSize() == 1)
                    s += 1;
                else
                    s += (s + m < n) ? m - gek : 1;
            } else {
                int gek = 0;
                int bc = backCheckBC(pat, tex, "false");
                int gs = backCheckGS(pat, k - 1);

                if (bc == -1 && gs > -1)
                    gek = gs;
                else if (bc > -1 && gs == -1)
                    gek = bc;
                else if (bc > -1 && gs > -1)
                    gek = min(bc, gs);
                else
                    gek = -1;


                s += max(1, j - gek);
            }
        }

        // stopwatch starts
        long finish = nanoTime();

        long timeElapsed = finish - start;
        System.out.println(tellTime(timeElapsed, "Boyer Moore"));

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

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

    private static int backCheckBC(DoublyLinkedList<String> pat, DoublyLinkedList<String> tex, String matched) {
        if (matched.equals("true"))
            pat.Last();

        int tempPos = 0;

        if (matched.equals("false"))
            tempPos = pat.GetPos();

        int jah = 0;
        for (int k = pat.GetPos(); k >= 0; k--) {

            if (pat.GetValue().equals(tex.GetValue())) {
                jah = pat.GetPos();
                if (matched.equals("false"))
                    pat.SetPos(tempPos);

                return jah;
            }

            pat.Prev();

        }

        if (matched.equals("false"))
            pat.SetPos(tempPos);

        return -1;
    }

    private static int backCheckGS(DoublyLinkedList<String> pat, int numMatched) {
        if (numMatched <= 0)
            return -1;

        String[] moonlightUH = new String[numMatched];
        int tempPos = pat.GetPos();
        pat.Last();
        for (int j = 0; j < numMatched; j++) {
            moonlightUH[j] = pat.GetValue();
            pat.Prev();
        }

        int posArray = numMatched - 1;
        for (int i = pat.GetPos(); i >= 0; i--) {
            while (pat.GetValue().equals(moonlightUH[posArray])) {
                posArray--;
                pat.Prev();
                if (posArray == -1)
                    return pat.GetPos();
            }

            pat.SetPos(i);
        }

        pat.SetPos(tempPos);
        return -1;
    }

    /*
    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) {

        // stopwatch starts
        long start = nanoTime();

        int numMatches = 0;

        int n = tex.GetSize();
        int m = pat.GetSize();

        if (m == 0)
            return null;

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

        int[] fails = failureFun(pat);

        // t = index in text
        // p = index in patten
        int p = 0;
        int t = 0;

        tex.First();
        while (t < n) {
            //tex.SetPos(t);
            pat.SetPos(p);
            if (tex.GetValue().equals(pat.GetValue())) {

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

                    if (DEBUG)
                        numMatches++;

                    t++;
                    tex.Next();
                    p = fails[p];
                } else {
                    t++;
                    tex.Next();
                    p++;
                }
            }

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

        // stopwatch stops
        long finish = nanoTime();

        long timeElapsed = finish - start;
        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 + " nanoseconds.";
    }
}