# Fastest string search algorithm invented by me. It is called ""Choudhary String Search Algorithm""

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;

/*
* 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;

long pfinger = 0;

for (int j = 0; j < patternSize; j++) {
t = (2 * t + 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 = 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;

char[] ctext = text.toCharArray();
int textLen = text.length();

ArrayList<Integer> al = new ArrayList<>();

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

// 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;

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) {
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());
lock1.notifyAll();
}
// wait until all input has been processed
synchronized (lock2) {
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 = "";
synchronized (lock1) {
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) {
//} else {
//}
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) {
synchronized (lock1) {
char ch = (char) (b);
String text = Character.toString(ch);
jta.append(text);
jta.setCaretPosition(jta.getDocument().getLength());
initialCaretPosition = jta.getCaretPosition();
}
} // end of outputToJTextArea

void configureJTextAreaForInputOutput() {

// 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
// we need to sleep here because of some threading issues
//try {
//} 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.setLocation(screenWidth / 5, screenHeight / 6);

jm = InitComponents.setupJMenuAndGet("Copy All to Clipboard");
jm.setBorder(BorderFactory.createLineBorder(Color.green, 2));
jmi = InitComponents.setupJMenuItemAndGet("Copy All to Clipboard");

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

return tmpJMB;

return tmpJM;

return tmpJMI;

}// 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 ====


• "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. Dec 1, 2021 at 11:41
• How did you test/profile your code?
– Mast
Dec 1, 2021 at 13:08
• @Mast, The test code is in the program itself. Please see the main() method.
– user245050
Dec 2, 2021 at 6:23
• @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.
– user245050
Dec 2, 2021 at 6:24
• 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. Dec 3, 2021 at 2:32

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.
• 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.

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

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

• 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. Mar 28 at 14:10
• @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.
– Pete
Apr 3 at 2:40
• @pacmaninbw I have edited my original post to also indicate that I have found the same algorithm in the public domain.
– Pete
Apr 3 at 2:46