-2
\$\begingroup\$

I have invented the fastest string search algorithm. It is called ""Choudhary String Search Algorithm (choudharyStringSearchAlgorithm)"". I have compared my algorithm with Brute Force Algorithm, Boyer Moore Algorithm, Rabin Karp Algorithm, and Knuth Morris Pratt Algorithm and my algorithm is the fastest.

You can copy this code and compile and run and see the results.

Can someone do the code review please. The code is below:


Fastest_String_Search_Algorithm.java


import java.math.BigInteger;
import java.util.*;
import java.io.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

class Algo {

    String name;
    int numTimesCameFastest;
    long timeTaken;

    Algo(String name, int num, long timeTaken) {

        this.name = name;
        this.numTimesCameFastest = num;
        this.timeTaken = timeTaken;

    } // end of Algo constructor

} // end of Algo

public class Fastest_String_Search_Algorithm {

    static int numAlgos = 5;
    static int ASIZE = 256;
    static LinkedHashMap<String, Algo> algoMap = new LinkedHashMap<String, Algo>();

    /*
     * Brute Force algorithm
     */
    public static int bruteForceStringSearchAlgorithm(char[] text, char[] pattern) {

        int n = text.length;
        int m = pattern.length;

        //brute force it -- loop over all characters in text O(n)
        for (int i = 0; i <= n - m; i++) { //index into the text
            //loop over all characters in pattern while characters match O(m)
            int k = 0; //index into the pattern
            while (k < m && text[i + k] == pattern[k]) {
                k++;
            }
            //if at end of pattern, then found  match starting at index i in text
            if (k == m) {
                return i;
            }
        } // end of for loop

        return -1;

    } // end of bruteForceStringSearchAlgorithm

    /*
     * Boyer Moore algorithm
     */
    public static void preBmBc(char[] pattern, int m, int[] bmBc) {

        int i = 0;

        for (i = 0; i < ASIZE; ++i) {
            bmBc[i] = m;
        }

        for (i = 0; i < m - 1; ++i) {
            bmBc[pattern[i]] = m - i - 1;
        }

    } // end of preBmBc

    public static void suffixes(char[] pattern, int m, int[] suff) {

        int f = 0;
        int g = 0;
        int i = 0;

        suff[m - 1] = m;
        g = m - 1;

        for (i = m - 2; i >= 0; --i) {
            if (i > g && suff[i + m - 1 - f] < i - g) {
                suff[i] = suff[i + m - 1 - f];
            } else {
                if (i < g) {
                    g = i;
                }
                f = i;
                while (g >= 0 && pattern[g] == pattern[g + m - 1 - f]) {
                    --g;
                }
                suff[i] = f - g;
            }
        }

    } // end of suffixes

    public static void preBmGs(char[] pattern, int m, int[] bmGs) {

        int i = 0;
        int j = 0;

        int[] suff = new int[m];

        suffixes(pattern, m, suff);

        for (i = 0; i < m; ++i) {
            bmGs[i] = m;
        }

        j = 0;

        for (i = m - 1; i >= 0; --i) {
            if (suff[i] == i + 1) {
                for (; j < m - 1 - i; ++j) {
                    if (bmGs[j] == m) {
                        bmGs[j] = m - 1 - i;
                    }
                }
            }
        }

        for (i = 0; i <= m - 2; ++i) {
            bmGs[m - 1 - suff[i]] = m - 1 - i;
        }

    } // end of preBmGs

    public static int boyerMooreStringSearchAlgorithm(char[] text, char[] pattern) {

        int i = 0;
        int j = 0;

        int m = pattern.length;
        int n = text.length;

        int[] bmGs = new int[m];
        int[] bmBc = new int[ASIZE];

        /* Preprocessing */
        preBmGs(pattern, m, bmGs);
        preBmBc(pattern, m, bmBc);

        /* Searching */
        j = 0;
        while (j <= n - m) {
            for (i = m - 1; (i >= 0) && (pattern[i] == text[i + j]); --i);
            if (i < 0) {
                return j;
            } else {
                j = j + ((bmGs[i] > (bmBc[text[i + j]] - m + 1 + i)) ? bmGs[i] : (bmBc[text[i + j]] - m + 1 + i));
            }
        }

        return -1;

    } // end of boyerMooreStringSearchAlgorithm

    /*
     * Rabin Karp algorithm
     */
    public static int rabinKarpStringSearchAlgorithm(char[] text, char[] pattern) {

        int patternSize = pattern.length; // m
        int textSize = text.length; // n

        long prime = (BigInteger.probablePrime((Integer.SIZE - Integer.numberOfLeadingZeros(patternSize)) + 1, new Random())).longValue();

        long r = 1;
        for (int i = 0; i < patternSize - 1; i++) {
            r *= 2;
            r = r % prime;
        }

        long[] t = new long[textSize];
        t[0] = 0;

        long pfinger = 0;

        for (int j = 0; j < patternSize; j++) {
            t[0] = (2 * t[0] + text[j]) % prime;
            pfinger = (2 * pfinger + pattern[j]) % prime;
        }

        int i = 0;
        boolean passed = false;

        int diff = textSize - patternSize;
        for (i = 0; i <= diff; i++) {
            if (t[i] == pfinger) {
                passed = true;
                for (int k = 0; k < patternSize; k++) {
                    if (text[i + k] != pattern[k]) {
                        passed = false;
                        break;
                    }
                }

                if (passed) {
                    return i;
                }
            }

            if (i < diff) {
                long value = 2 * (t[i] - r * text[i]) + text[i + patternSize];
                t[i + 1] = ((value % prime) + prime) % prime;
            }
        }

        return -1;

    } // end of rabinKarpStringSearchAlgorithm

    /*
     * Knuth Morris Pratt algorithm
     */
    public static int[] KnuthMorrisPrattShift(char[] pattern) {

        int patternSize = pattern.length;

        int[] shift = new int[patternSize];
        shift[0] = 1;

        int i = 1, j = 0;

        while ((i + j) < patternSize) {
            if (pattern[i + j] == pattern[j]) {
                shift[i + j] = i;
                j++;
            } else {
                if (j == 0) {
                    shift[i] = i + 1;
                }

                if (j > 0) {
                    i = i + shift[j - 1];
                    j = (((j - shift[j - 1]) > 0) ? (j - shift[j - 1]) : 0);
                } else {
                    i = i + 1;
                    j = 0;
                }
            }
        }

        return shift;

    } // end of KnuthMorrisPrattShift

    public static int knuthMorrisPrattStringSearchAlgorithm(char[] text, char[] pattern) {

        int patternSize = pattern.length; // m
        int textSize = text.length; // n

        int i = 0, j = 0;

        int[] shift = KnuthMorrisPrattShift(pattern);

        while ((i + patternSize) <= textSize) {
            while (text[i + j] == pattern[j]) {
                j += 1;
                if (j >= patternSize) {
                    return i;
                }
            }

            if (j > 0) {
                i += shift[j - 1];
                j = (((j - shift[j - 1]) > 0) ? (j - shift[j - 1]) : 0);
            } else {
                i++;
                j = 0;
            }
        }

        return -1;

    } // end of knuthMorrisPrattStringSearchAlgorithm

    /*
     * Choudhary algorithm
     */
    public static int choudharyStringSearchAlgorithm(char[] text, char[] pattern) {

        int i = 0;
        int j = 0;

        int text_len = text.length;
        int pattern_len = pattern.length;

        int pi_44 = pattern_len - 1;

        int[] skip_table = new int[ASIZE];

        // preprocess pattern and fill skip_table
        for (i = 0; i < ASIZE; i++) {
            skip_table[i] = -1;
        }

        for (i = 0; i < pattern_len; i++) {
            skip_table[pattern[i]] = pattern_len - 1 - i;
        }

        // now search
        for (i = 0; i < text_len; i++) {

            if ((text_len - i) < pattern_len) {
                return -1;
            }

            if (pattern[pi_44] != text[i + pi_44]) {
                if (skip_table[(int) (text[i + pi_44])] == -1) { // this character doesn't occur in pattern, so skip
                    i = i + pi_44;
                } else if (skip_table[(int) (text[i + pi_44])] > 0) {
                    i = i + skip_table[(int) (text[i + pi_44])] - 1;
                }
                continue;
            }

            for (j = pi_44 - 1; j >=0; j--) {
                if (pattern[j] != text[i + j]) {
                    if (skip_table[(int) (text[i + j])] == -1) { // this character doesn't occur in pattern, so skip
                        i = i + j;
                    }
                    break;
                }
            } // end of inner for loop

            if (j == -1) { //string matched
                return i;
            }

        } // end of outer for loop

        return -1;

    } // end of choudharyStringSearchAlgorithm

    public static Algo getFastestAlgoEntryFromMap() {

        Algo tmpAlgo = null;
        Algo fastestAlgo = algoMap.get("BruteForce");

        for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
            tmpAlgo = entry.getValue();
            if (tmpAlgo.timeTaken < fastestAlgo.timeTaken) {
                fastestAlgo = tmpAlgo;
            }
        }

        return fastestAlgo;

    } // end of getFastestAlgoEntryFromMap

    public static void initializeTimeTakenOfAllMapEntries() {

        for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
            entry.getValue().timeTaken = 0;
        }

    } // end of initializeTimeTakenOfAllMapEntries

    public static void initializeNumTimesCameFastestOfAllMapEntries() {

        for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
            entry.getValue().numTimesCameFastest = 0;
        }

    } // end of initializeNumTimesCameFastestOfAllMapEntries

    public static void initializeAlgoMap() {

        algoMap.put("BruteForce", new Algo("Brute Force", 0, 0));
        algoMap.put("BoyerMoore", new Algo("Boyer Moore", 0, 0));
        algoMap.put("RabinKarp", new Algo("Rabin Karp", 0, 0));
        algoMap.put("KnuthMorrisPratt", new Algo("KnuthMorrisPratt", 0, 0));
        algoMap.put("Choudhary", new Algo("Choudhary", 0, 0));

    } // end of initializeAlgoMap

    public static void main(String[] args) {

        Console c = new Console();
        c.createAndShowConsole();
        Console.jf.setTitle("Console");

        Algo tmpAlgo = null;

        int correctIndex = -1;
        int index = -1;

        long startTime = 0;
        long endTime = 0;

        String text = "This past summer, I had the privilege of participating in the University of Notre Dame's Research Experience for Undergraduates (REU) program . Under the mentorship of Professor Wendy Bozeman and Professor Georgia Lebedev from the department of Biological Sciences, my goal this summer was to research the effects of cobalt iron oxide cored (CoFe2O3) titanium dioxide (TiO2) nanoparticles as a scaffold for drug delivery, specifically in the delivery of a compound known as curcumin, a flavonoid known for its anti-inflammatory effects. As a high school student trying to find a research opportunity, it was very difficult to find a place that was willing to take me in, but after many months of trying, I sought the help of my high school biology teacher, who used his resources to help me obtain a position in the program.              Using equipment that a high school student could only dream of using, I was able to map apoptosis (programmed cell death) versus necrosis (cell death due to damage) in HeLa cells, a cervical cancer line, after treating them with curcumin-bound nanoparticles. Using flow cytometry to excite each individually suspended cell with a laser, the scattered light from the cells helped to determine which cells were living, had died from apoptosis or had died from necrosis. Using this collected data, it was possible to determine if the curcumin and/or the nanoparticles had played any significant role on the cervical cancer cells. Later, I was able to image cells in 4D through con-focal microscopy. From growing HeLa cells to trying to kill them with different compounds, I was able to gain the hands-on experience necessary for me to realize once again why I love science.              Living on the Notre Dame campus with other REU students, UND athletes, and other summer school students was a whole other experience that prepared me for the world beyond high school. For 9 weeks, I worked, played and bonded with the other students, and had the opportunity to live the life of an independent college student.               Along with the individually tailored research projects and the housing opportunity, there were seminars on public speaking, trips to the Fermi National Accelerator Laboratory, and one-on-one writing seminars for the end of the summer research papers we were each required to write. By the end of the summer, I wasn't ready to leave the research that I was doing. While my research didn't yield definitive results for the effects of curcumin on cervical cancer cells, my research on curcumin-functionalized CoFe2O4/TiO2 core-shell nanoconjugates indicated that there were many unknown factors affecting the HeLa cells, and spurred the lab to expand their research into determining whether or not the timing of the drug delivery mattered and whether or not the position of the binding site of the drugs would alter the results. Through this summer experience, I realized my ambition to pursue a career in research. I always knew that I would want to pursue a future in science, but the exciting world of research where the discoveries are limitless has captured my heart. This school year, the REU program has offered me a year-long job, and despite my obligations as a high school senior preparing for college, I couldn't give up this offer, and so during this school year, I will be able to further both my research and interest in nanotechnology. I believe that humans will always have the ability to rise above any situation, because life is what you make of it. We don't know what life is or why we are in this world; all we know, all we feel, is that we must protect it anyway we can. Buddha said it clearly: \"Life is suffering.\" Life is meant to be challenging, and really living requires consistent work and review. By default, life is difficult because we must strive to earn happiness and success. Yet I've realized that life is fickler than I had imagined; it can disappear or change at any time. Several of my family members left this world in one last beating symphony; heart attacks seem to be a trend in my family. They left like birds; laughing one minute and in a better place the next. Steve Jobs inspired me, when in his commencement address to Stanford University in 2005, he said \\\"Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma--which is living with the results of other people's thinking.\\\" I want to make mistakes, because that is how I learn; I want to follow the beat of my own drum even if it is \\\"out of tune.\\\" The important thing is to live without regrets, so when my heart ceases to beat, it will make one last happy note and move on. I want to live my life daily. Every day I want to live. Every morning when I wake up, I want to be excited by the gift of a new day. I know I am being idealistic and young, and that my philosophy on life is comparable to a calculus limit; I will never reach it. But I won't give up on it because, I can still get infinitely close and that is amazing. Every day is an apology to my humanity; because I am not perfect, I get to try again and again to \\\"get it right.\\\" I breathe the peace of eternity, knowing that this stage is temporary; real existence is continuous. The hourglass of life incessantly trickles on and we are powerless to stop it. So, I will forgive and forget, love and inspire, experience and satire, laugh and cry, accomplish and fail, live and die. This is how I want to live my life, with this optimistic attitude that every day is a second chance. All the time, we have the opportunity to renew our perspective on life, to correct our mistakes, and to simply move on. Like the phoenix I will continue to rise from the ashes, experienced and renewed. I will not waste time for my life is already in flux. In all its splendor The Phoenix rises In a burst of orange and yellow It soars in the baby blue sky Heading to that Great Light Baptized in the dance of time Fearless, eternal, beautiful It releases a breathtaking aurora And I gasp at the enormity In most conventional classrooms, we are taught to memorize material. We study information to regurgitate it on a test and forget it the following day. I thought this was learning. But this past summer, I realized I was wrong.  I attended the SPK Program, a five-week enrichment program with New Jersey's best and brightest students. I lived on a college campus with 200 students and studied a topic. I selected Physical Science. On the first day of class, our teacher set a box on the table and poured water into the top, and nothing came out. Then, he poured more water in, and everything slowly came out. We were told to figure out what had happened with no phones or textbooks, just our brains. We worked together to discover in the box was a siphon, similar to what is used to pump gas. We spent the next weeks building solar ovens, studying the dynamic of paper planes, diving into the content of the speed of light and space vacuums, among other things. We did this with no textbooks, flashcards, or information to memorize. During those five weeks, we were not taught impressive terminology or how to ace the AP Physics exam. We were taught how to think. More importantly, we were taught how to think together. Learning is not memorization or a competition. Learning is working together to solve the problems around us and better our community. To me, learning is the means to a better future, and that's exciting. As I sip a mug of hot chocolate on a dreary winter's day, I am already planning in my mind what I will do the next summer.  I briefly ponder the traditional routes, such as taking a job or spending most of the summer at the beach.  However, I know that I want to do something unique.  I am determined to even surpass my last summer, in which I spent one month with a host family in Egypt and twelve days at a leadership conference in New York City  The college courses I have taken at Oregon State University since the summer after 7th grade will no longer provide the kind of challenge I seek. Six months later, I step off the airplane to find myself surrounded by palm trees, with a view of the open-air airport.  I chuckle to myself about the added bonus of good weather, but I know I have come to Palo Alto, California, with a much higher purpose in mind.  I will spend six weeks here in my glory, not only studying and learning, but actually pursuing new knowledge to add to the repertoire of mankind.  Through the Stanford Institutes of Medicine Summer Research Program, I will earn college credit by conducting original molecular biology research, writing my own research paper, and presenting my findings in a research symposium. I decided to spend my summer doing research because I knew that I liked scientific thought, and that I would passionately throw myself into any new challenge.  I always want to know more - to probe deeper into the laws of the universe, to explore the power and beauty of nature, to solve the most complicated problems.  I have an insatiable curiosity and a desire to delve deeper down in the recesses of my intellect.  At the Summer Research Program, I found out how much I enjoy thinking critically, solving problems, and applying my knowledge to the real world.  While pursuing research in California, I was also able to meet many similarly motivated, interesting people from across the United States and abroad.  As I learned about their unique lifestyles, I also shared with them the diverse perspectives I have gained from my travel abroad and my Chinese cultural heritage.  I will never forget the invaluable opportunity I had to explore California along with these bright people. I could have easily chosen to spend that summer the traditional way; in fact, my parents even tried to persuade me into taking a break.  Instead, I chose to do molecular biology research at Stanford University.  I wanted to immerse myself in my passion for biology and dip into the infinitely rich possibilities of my mind.  This challenge was so rewarding to me, while at the same time I had the most fun of my life, because I was able to live with people who share the same kind of drive and passion as I do. I held my breath as my steady hands gently nestled the crumbly roots of the lettuce plant into the soil trench that I shoveled moments before. Rainwater and sweat dripped from my brow as I meticulously patted and pressed the surrounding earth, stamping the leafy green creature into its new home. After rubbing the gritty soil off of my hands, I looked at Brian, a co-volunteer and nonverbal 20-year-old with autism, who extended his arm for a high-five. In the year that I've been working with him, I've watched him revel in planting, nurturing, and eventually harvesting his veggies, especially the grape tomatoes, which we enjoy eating fresh off the vine! Upon walking to the next row of hollowed cavities, we were not contemplating the lengthy work that lay ahead, but rather, we sought to liberate the helpless lettuces, imprisoned in produce cartons that were too small for them to grow in. Finally, after taking a step back to admire the day's last plant, my chest swelled as a wave of contentment flushed through my body.  My love for gardening began when I moved to Georgia during my sophomore year. In the time I've spent learning how to garden, I've developed an affinity for watching my vegetables grow to maturity, eager to be harvested and sold at the Saturday market. Though many see gardening as tedious busywork, I find it meditative, as I lose track of time while combining peat moss and soil in the garden's compost mixer. Saturday morning garden work has become a weekend ritual, ridding me of all extraneous responsibilities. My body goes into autopilot as I let my mind wander. I don't actively focus on focusing, but rather I observe myself internally digest the week's events. I'm a bystander to fireworks of thought that explode in my mind as my perception of important matters becomes trivial. Sometimes, it's the physics midterm that suddenly seems less daunting or the deadlines I need to meet for my Spanish project that push back farther. Other times, I contemplate alternative endings to conversations or make perfect sense of the calculus answer that was at the tip of my tongue in class.  I met Brian, a close friend of mine who also basks in the tranquility of nature, through my gardening endeavors. While we aren't able to communicate verbally, we speak the language of earth, water, peat, and seedlings. He doesn't speak with words, but his face tells stories of newly found purpose and acceptance, a pleasant contrast to the typical condescension and babying he feels by those who don't think he's capable of independent thought.  Throughout my time in the garden with Brian, I began to understand that he, like everyone, has a particular method of communicating. There are the obvious spoken languages, body languages, facial expressions, and interactions we share on a day-to-day basis that reflect who we are and communicate what we represent. Brian expresses himself through various manifestations of unspoken language that he uses to signal how he feels or what he wants. But the nuanced combinations of different methods of communicating are oftentimes overlooked, raising a barrier to mutual understanding that prevents one from being capable of truly connecting with others. I began to understand that in order to reach people, I have to speak in their language, be it verbally or otherwise. Working with Brian over the past year has made me more aware that people can have difficulty expressing themselves. I found that I can positively lead people if I can communicate with them, whether on the track or in my Jewish youth group discussions. As I move into the next phases of my life, I hope to bring these skills with me because, in order to effectuate positive change in my community, I learned that I must speak in the language of those around me. Those are the words Brian taught me.";
        char[] ctext = text.toCharArray();
        int textLen = text.length();

        ArrayList<Integer> al = new ArrayList<>();
        al.add(4);
        al.add(8);
        al.add(16);
        al.add(32);
        al.add(36);
        al.add(40);
        al.add(48);
        al.add(56);
        al.add(64);
        al.add(128);
        al.add(256);
        al.add(512);
        al.add(1024);

        int patternLen = 0;

        String pattern = "";
        char[] cpattern = null;

        int totalNumberOfRunsPerPattern = 25;

        // initialize algo map
        initializeAlgoMap();

        while (al.isEmpty() != true) {

            patternLen = al.remove(0);

            System.out.println();
            System.out.println("===================== Summary (Text Len: " + textLen + ", Pattern Len: " + patternLen + ", Total number of runs per pattern: " + totalNumberOfRunsPerPattern + ") =====================");

            initializeNumTimesCameFastestOfAllMapEntries();

            // initialize time taken by all algorithms to zero.
            initializeTimeTakenOfAllMapEntries();

            pattern = text.substring(textLen - patternLen);
            cpattern = pattern.toCharArray();

            correctIndex = text.indexOf(pattern);
            if (correctIndex == -1) {
                System.out.println("Pattern not found by indexOf() method...Exiting...");
                return;
            }

            for (int j = 0; j < totalNumberOfRunsPerPattern; j++) {

                Console.jf.setTitle("Console (Current Run Number: " + (j + 1) + " / " + totalNumberOfRunsPerPattern + ", Pattern Len: " + patternLen + ")");

                // Brute Force algorithm
                startTime = System.nanoTime();
                index = bruteForceStringSearchAlgorithm(ctext, cpattern);
                endTime = System.nanoTime();

                if (index != correctIndex) {
                    System.out.println("bruteForceStringSearchAlgorithm is not correct...Exiting...");
                    return;
                }

                tmpAlgo = algoMap.get("BruteForce");
                tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);

                // Boyer Moore algorithm
                startTime = System.nanoTime();
                index = boyerMooreStringSearchAlgorithm(ctext, cpattern);
                endTime = System.nanoTime();

                if (index != correctIndex) {
                    System.out.println("boyerMooreStringSearchAlgorithm is not correct...Exiting...");
                    return;
                }

                tmpAlgo = algoMap.get("BoyerMoore");
                tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);

                // Rabin Karp algorithm
                startTime = System.nanoTime();
                index = rabinKarpStringSearchAlgorithm(ctext, cpattern);
                endTime = System.nanoTime();

                if (index != correctIndex) {
                    System.out.println("rabinKarpStringSearchAlgorithm is not correct...Exiting...");
                    return;
                }

                tmpAlgo = algoMap.get("RabinKarp");
                tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);

                // Knuth Morris Pratt algorithm
                startTime = System.nanoTime();
                index = knuthMorrisPrattStringSearchAlgorithm(ctext, cpattern);
                endTime = System.nanoTime();

                if (index != correctIndex) {
                    System.out.println("knuthMorrisPrattStringSearchAlgorithm is not correct...Exiting...");
                    return;
                }

                tmpAlgo = algoMap.get("KnuthMorrisPratt");
                tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);

                // Choudhary algorithm
                startTime = System.nanoTime();
                index = choudharyStringSearchAlgorithm(ctext, cpattern);
                endTime = System.nanoTime();

                if (index != correctIndex) {
                    System.out.println("choudharyStringSearchAlgorithm is not correct...Exiting...");
                    return;
                }

                tmpAlgo = algoMap.get("Choudhary");
                tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);

                tmpAlgo = getFastestAlgoEntryFromMap();
                tmpAlgo.numTimesCameFastest = tmpAlgo.numTimesCameFastest + 1;

            } // end of for loop j < totalNumberOfRunsPerPattern

            System.out.println();
            for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
                tmpAlgo = entry.getValue();
                float percent = (((((float) (tmpAlgo.numTimesCameFastest)) * 100) / totalNumberOfRunsPerPattern) * 100) / 100;
                System.out.println(tmpAlgo.name + " algorithm is fastest \"" + percent + "%\" of times.");
            }

            System.out.println();
            System.out.println("===================== End of Summary =====================");

        } // end of while true

    } // end of main

} // end of Fastest_String_Search_Algorithm

class Console implements KeyListener, ActionListener {

    Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
    int screenWidth = screenSize.width;
    int screenHeight = screenSize.height;

    String title = null;
    String text = null;

    static JFrame jf = null;
    JTextArea jta = null;
    JScrollPane jsp = null;
    JMenuBar jmb = null;
    JMenu jm = null;
    JMenuItem jmi = null;

    // key codes
    int BACKSPACE = 8;
    int ENTER = 10;
    int PG_UP = 33; // do nothing for this key pressed
    int PG_DN = 34; // do nothing for this key pressed
    int END = 35;
    int HOME = 36;
    int LEFT_ARROW = 37;
    int UP_ARROW = 38; // do nothing for this key pressed
    //int RIGHT_ARROW = 39; // handled by JTextArea
    int DOWN_ARROW = 40; // do nothing for this key pressed

    int CTRL = 128;
    int A = 65; // disable ctrl-a
    int H = 72; // handle ctrl-h
    //int DELETE = 127; // handled by JTextArea

    int initialCaretPosition = 0;
    int endOfInputCaretPosition = 0;
    Object lock1 = new Object();
    Object lock2 = new Object();
    boolean inputAvailable = false;
    byte[] b = null;
    int len = -1;
    int indexIntoByteArray = -1;
    boolean newLineSent = false;
    byte endOfInput = -1;
    byte newLine = 10;
    boolean enterAlreadyPressedEarlier = false;

    long Id_keyPressed = 0;
    long Id_getNextByteFromJTextArea = 0;
    long Id_outputToJTextArea = 0;

    public void actionPerformed(ActionEvent ae) {
        int cCurrPos = jta.getCaretPosition();
        jta.selectAll();
        jta.copy();
        jta.select(cCurrPos, cCurrPos);
    } // end of actionPerformed

    public void keyTyped(KeyEvent ke) {
    } // end of keyTyped

    public void keyReleased(KeyEvent ke) {
    } // end of keyReleased

    public void keyPressed(KeyEvent ke) {
        Id_keyPressed = Thread.currentThread().getId();
        int keyCode = ke.getKeyCode();
        if ((keyCode == PG_UP) || (keyCode == PG_DN) || (keyCode == UP_ARROW) || (keyCode == DOWN_ARROW) || ((keyCode == A) && (ke.getModifiersEx() == CTRL))) {
            ke.consume();
        } else if ((keyCode == LEFT_ARROW) || (keyCode == BACKSPACE) || ((keyCode == H) && (ke.getModifiersEx() == CTRL))) {
            synchronized (lock1) {
                if (jta.getCaretPosition() <= initialCaretPosition) {
                    ke.consume();
                }
            } // end of synchronized block
        } else if (keyCode == HOME) {
            synchronized (lock1) {
                jta.setCaretPosition(initialCaretPosition);
                ke.consume();
            } // end of synchronized block
        } else if (keyCode == END) {
            synchronized (lock1) {
                jta.setCaretPosition(jta.getDocument().getLength());
                ke.consume();
            } // end of synchronized block
        } else if (keyCode == ENTER) {
            // this if block should not exit until all the input has been
            // processed.
            synchronized (lock1) {
                inputAvailable = true;
                endOfInputCaretPosition = jta.getDocument().getLength();
                //if ((endOfInputCaretPosition - initialCaretPosition) == 1) {
                // only newline was entered, so increment initialCaretPosition
                if ((enterAlreadyPressedEarlier == true) && (endOfInputCaretPosition - initialCaretPosition) > 0) {
                    // need to increment initialCaretPosition by 1 to account for last enter pressed
                    initialCaretPosition++;
                }
                jta.setCaretPosition(jta.getDocument().getLength());
                enterAlreadyPressedEarlier = true;
                lock1.notifyAll();
            }
            // wait until all input has been processed
            synchronized (lock2) {
                //if (Thread.holdsLock(lock2) == true) { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock2 is held"); } else { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock2 is _not_ held"); }
                try {
                    lock2.wait();
                } catch (Exception e) {
                    //System.out.println("Exception (debug:1): " + e.getMessage());
                }
            }
        } // end of if else if
    } // end of keyPressed

    byte getNextByteFromJTextArea() {
        String s = "";
        Id_getNextByteFromJTextArea = Thread.currentThread().getId();
        synchronized (lock1) {
            //if (Thread.holdsLock(lock1) == true) { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock1 is held"); } else { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock1 is _not_ held"); }
            if (inputAvailable == false) {
                try {
                    lock1.wait();
                } catch (Exception e) {
                    //System.out.println("Excpetion (debug:2): " + e.getMessage());
                    //System.exit(1);
                } // end of try catch
            } // end of if inputAvailable

            if (newLineSent == true) {
                // send endOfInput now, all input has been prcocessed, anyone
                // waiting on lock2 should be woken up and some variables
                // should be re-initialized
                newLineSent = false;
                b = null;
                len = -1;
                indexIntoByteArray = -1;
                inputAvailable = false;
                initialCaretPosition = jta.getDocument().getLength();
                endOfInputCaretPosition = jta.getDocument().getLength();
                synchronized (lock2) {
                    //if (Thread.holdsLock(lock2) == true) {
                    //    System.out.println("lock2 is held..2..Thread id = " + Thread.currentThread().getId());
                    //} else {
                    //    System.out.println("lock2 is ___not___ held..2..Thread id = " + Thread.currentThread().getId());
                    //}
                    lock2.notifyAll();
                    return endOfInput;
                }
            } // end of if newLineSent

            if (len == -1) { // read input
                len = endOfInputCaretPosition - initialCaretPosition;
                try {
                    s = jta.getText(initialCaretPosition, len);
                    b = s.getBytes(); // enter is still getting processed, the text area
                    // hasn't been updated with the enter, so send a
                    // newline once all bytes have been sent.
                } catch (Exception e) {
                    //System.out.println("Exception (debug:3): " + e.getMessage());
                    if (b != null) {
                        Arrays.fill(b, (byte) (-1));
                    }
                } // end of try catch
            } // end of if len == -1

            // if control reaches here then it means that we have to send a byte
            indexIntoByteArray++;
            if (indexIntoByteArray == len) { // send newLine as all input have been sent already
                newLineSent = true;
                return newLine;
            }
            if (b[indexIntoByteArray] == newLine) {
                newLineSent = true;
            }
            return b[indexIntoByteArray];
        } // end of synchronized block
    } // end of getNextByteFromJTextArea

    void outputToJTextArea(byte b) {
        Id_outputToJTextArea = Thread.currentThread().getId();
        synchronized (lock1) {
            char ch = (char) (b);
            String text = Character.toString(ch);
            jta.append(text);
            jta.setCaretPosition(jta.getDocument().getLength());
            initialCaretPosition = jta.getCaretPosition();
            enterAlreadyPressedEarlier = false;
        }
    } // end of outputToJTextArea

    void configureJTextAreaForInputOutput() {
        jta.addKeyListener(this);

        // remove all mouse listeners
        for (MouseListener listener : jta.getMouseListeners()) {
            //outputToJTextArea(jta, "\nRemoving mouse listener\n");
            jta.removeMouseListener(listener);
        }

        // remove all mouse motion listeners
        for (MouseMotionListener listener : jta.getMouseMotionListeners()) {
            //outputToJTextArea(jta, "\nRemoving mouse motion listener\n");
            jta.removeMouseMotionListener(listener);
        }

        // remove all mouse wheel listeners
        for (MouseWheelListener listener : jta.getMouseWheelListeners()) {
            //outputToJTextArea(jta, "\nRemoving mouse wheel listener\n");
            jta.removeMouseWheelListener(listener);
        }

        System.setIn(new InputStream() {
            @Override
            public int read() {
                // we need to sleep here because of some threading issues
                //try {
                //    Thread.sleep(1);
                //} catch (Exception e) {
                //System.out.println("Exception (debug:4): " + e.getMessage());
                //}
                byte b = getNextByteFromJTextArea();
                return ((int) (b));
            }
        });

        System.setOut(new PrintStream(new OutputStream() {
            @Override
            public void write(int b) {
                outputToJTextArea((byte) (b));
            }
        }));

        System.setErr(new PrintStream(new OutputStream() {
            @Override
            public void write(int b) {
                outputToJTextArea((byte) (b));
            }
        }));

    } // end of configureJTextAreaForInputOutput

    void createAndShowConsole() {
        title = "Console";
        jf = InitComponents.setupJFrameAndGet(title, (3 * screenWidth) / 4, (3 * screenHeight) / 4);

        jta = InitComponents.setupJTextAreaAndGet("", 5000, 100, true, true, true, false, 0, 0, 0, 0);
        configureJTextAreaForInputOutput();

        jsp = InitComponents.setupScrollableJTextAreaAndGet(jta, 10, 10, (3 * screenWidth) / 4 - 33, (3 * screenHeight) / 4 - 79);
        jsp.setHorizontalScrollBarPolicy(ScrollPaneConstants.HORIZONTAL_SCROLLBAR_AS_NEEDED);
        jsp.setVerticalScrollBarPolicy(ScrollPaneConstants.VERTICAL_SCROLLBAR_ALWAYS);
        jf.add(jsp);
        //jf.setLocation(screenWidth / 5, screenHeight / 6);

        jmb = InitComponents.setupJMenuBarAndGet();
        jm = InitComponents.setupJMenuAndGet("Copy All to Clipboard");
        jm.setBorder(BorderFactory.createLineBorder(Color.green, 2));
        jmi = InitComponents.setupJMenuItemAndGet("Copy All to Clipboard");
        jm.add(jmi);
        jmb.add(jm);
        jmi.addActionListener(this);
        jf.setJMenuBar(jmb);

        jf.setLocationRelativeTo(null);
        jf.setVisible(true);
    } // end of createAndShowConsole

} // end of Console

class InitComponents {

    public static JFrame setupJFrameAndGet(String title, int width, int height) {
        JFrame tmpJF = new JFrame(title);
        tmpJF.setSize(width, height);
        tmpJF.setLocationRelativeTo(null);
        tmpJF.setLayout(null);
        tmpJF.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        return tmpJF;
    } // end of setupJFrameAndGet

    public static JTextArea setupJTextAreaAndGet(String text, int rows, int columns, boolean setEditableFlag, boolean setLineWrapFlag, boolean setWrapStyleWordFlag, boolean setBoundsFlag, int xpos, int ypos, int width, int height) {
        JTextArea tmpJTA = new JTextArea(text, rows, columns);
        tmpJTA.setEditable(setEditableFlag);
        tmpJTA.setLineWrap(setLineWrapFlag);
        tmpJTA.setWrapStyleWord(setWrapStyleWordFlag);
        if (setBoundsFlag == true) {
            tmpJTA.setBounds(xpos, ypos, width, height);
        }
        return tmpJTA;
    } // end of setupJTextAreaAndGet

    public static JScrollPane setupScrollableJTextAreaAndGet(JTextArea jta, int xpos, int ypos, int width, int height) {
        JScrollPane tmpJSP = new JScrollPane(jta);
        tmpJSP.setBounds(xpos, ypos, width, height);
        return tmpJSP;
    } // end of setupScrollableJTextAreaAndGet

    public static JMenuBar setupJMenuBarAndGet() {
        JMenuBar tmpJMB = new JMenuBar();
        return tmpJMB;
    } // end of setupJMenuBarAndGet

    public static JMenu setupJMenuAndGet(String text) {
        JMenu tmpJM = new JMenu(text);
        return tmpJM;
    } // end of setupJMenuAndGet

    public static JMenuItem setupJMenuItemAndGet(String text) {
        JMenuItem tmpJMI = new JMenuItem(text);
        return tmpJMI;
    } // end of setupJMenuItemAndGet

}// end of InitComponents


Results


== Summary (Text Len: 14013, Pattern Len: 4, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "44.0%" of times.
Choudhary algorithm is fastest "56.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 8, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "92.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "8.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 16, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 32, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 36, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 40, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 48, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 56, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "16.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "84.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 64, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 128, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 256, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 512, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.

==== End of Summary ====

== Summary (Text Len: 14013, Pattern Len: 1024, Total number of runs per pattern: 25) ==

Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.

==== End of Summary ====

\$\endgroup\$
11
  • 9
    \$\begingroup\$ "I have invented the fastest string search algorithm" - My gut feeling: If that were true, I wouldn't hear about it on codereview :-P. Some explanation in addition to the code would be helpful. \$\endgroup\$ Commented Dec 1, 2021 at 11:41
  • 3
    \$\begingroup\$ How did you test/profile your code? \$\endgroup\$
    – Mast
    Commented Dec 1, 2021 at 13:08
  • \$\begingroup\$ @Mast, The test code is in the program itself. Please see the main() method. \$\endgroup\$
    – user245050
    Commented Dec 2, 2021 at 6:23
  • \$\begingroup\$ @Kelly, Writing a paper and then giving it out for peer review is a lot of work. So, I didn't do that. I just put the code here for review. \$\endgroup\$
    – user245050
    Commented Dec 2, 2021 at 6:24
  • 2
    \$\begingroup\$ Given that the first sentence is prima facie ludicrous, this is unserious and I'm not wasting my time with it. I will happily eat my words when you return with a peer-reviewed paper published in a reputable journal. \$\endgroup\$
    – Eric Stein
    Commented Dec 3, 2021 at 2:32

2 Answers 2

13
\$\begingroup\$

Maybe your algorithm is really fast, but this site isn't about algorithm review, it's about code review.

And a "fastest string search algorithm" should come in a software package of an equally high quality, which it doesn't. The current code quality is far below acceptability for any "production level" usage.

  • A string search algorithm should be in a ready-to-use library form.
  • It should come in a class with one public method like int search(CharSequence text, CharSequence pattern).
  • Requiring char[] instead of CharSequence makes usage clumsier, and slower in most use cases, as the caller first has to convert any String to char[].
  • A string search class should not contain multiple competing algorithms. If you have multiple algorithms, each should come in its own class, with a common interface that they all implement.
  • You should add Javadoc for public classes and methods.
  • Code should go into a package like e.g. com.stackexchange.codereview.amit.stringsearch.
  • Code for performance comparison doesn't belong into your string search class, but into a separate testing class.
  • Performance comparison based on a single test text is useless. Anyway, Java performance testing is a tricky thing, and it's very easy to get wrong results.
  • If you do performance comparisons, make sure to include Java's own String.indexOf() method as a performance reference.
  • The Swing user interface has nothing to do with the search algorithm. It's useless to any potential string-search user.
  • Your naming doesn't follow the established Java Naming conventions (e.g. skip_table should be skipTable).
  • A variable named pi_44, with its value being the pattern length minus one, is a no-go. It has nothing to do with the mathematical number PI, nor the number 44.
  • You should avoid wildcard imports like import java.util.*;, as they are a quality risk.
  • Test cases like your long text variable don't belong into a worker class, but should be separated. There are lots of unit testing frameworks available in Java. Use one of them for that purpose.
  • You should make sure the algorithm is not only fast, but also correct, by creating lots of test cases, and comparing your results with a trusted reference (e.g. String.indexOf()). Be sure to include corner cases like empty pattern, empty text, matching and non-matching patterns, non-ASCII characters and so on.

If you're sure that your algorithm is as good as promised, you should invest the time to bring the code quality up to an adequate level. And I'll be happy to review the improved version here.

\$\endgroup\$
1
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$
    – Mast
    Commented Dec 2, 2021 at 16:49
1
\$\begingroup\$

I know it's an old post but it intrigued me.. I don't think it too fast at all. I ran a test where I searched the full text of Moby Dick (line by line) 500 consecutive times looking for the word "whale". I re-wrote the algorithm in Fortran and compared it to a few others in my library of string searching software. Here's my results (in seconds); Colussi 5.60900 Choudhary 3.43800 Knuth Moore Pratt 1.23500 Not so Naïve 0.86000 Karp-Rabin 0.76600 Boyer Moore 0.76500 Shift-Or Search 0.23500 In built Search 0.00000 The Average line length was 74 characters, the whole file was read into memory to avoid i/o impacts. EDIT: I have since found that the alogithm is not a novel or new one. It is the "Raita" algorithm. You may find the C language code for it at http://www-igm.univ-mlv.fr/~lecroq/string/node22.html#SECTION00220

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Technically we are looking for observations about the code. You did make an observation that it could be faster, but comparing Java to Fortran may not be a valid observation. \$\endgroup\$
    – pacmaninbw
    Commented Mar 28, 2023 at 14:10
  • \$\begingroup\$ @pacmaninbw - Sorry for the misunderstanding. I rewrote it in Fortran then compared it to other algorithms that I had written in Fortran. No Java to Fortran comparisons were made. \$\endgroup\$
    – Pete
    Commented Apr 3, 2023 at 2:40
  • \$\begingroup\$ @pacmaninbw I have edited my original post to also indicate that I have found the same algorithm in the public domain. \$\endgroup\$
    – Pete
    Commented Apr 3, 2023 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.