Program to Implement K-Naive Algorithm in Java

In this post, we’ll implement the K-Naive (Brute-Force) string matching algorithm in Java. This is the simplest form of string search, where we check for the presence of a pattern in a text by checking one by one at every possible position.

What is the K-Naive (Brute-Force) Algorithm?

The Brute-Force algorithm searches for a substring (pattern) within a larger string (text) by checking for a match at every position in the text. It is simple to understand and implement but can be inefficient for large inputs.

Java Code Implementation

import java.io.*;

// Class containing the brute-force string matching function
class BruteForceMatcher {

    // Method to search for the pattern in the text using brute-force approach
    int bruteForceSearch(String text, String pattern) {
        int textLength = text.length();
        int patternLength = pattern.length();
        int flag = 0;

        // Loop through the text
        for (int i = 0; i <= textLength - patternLength; i++) {
            // Check if first character matches
            if (pattern.charAt(0) == text.charAt(i)) {
                // If pattern has only one character, match found
                if (patternLength == 1)
                    return i + 1;

                // Check the remaining characters of the pattern
                for (int k = 1; k < patternLength; k++) {
                    if (pattern.charAt(k) == text.charAt(i + k))
                        flag = k + 1;
                }

                // If all characters matched, return the position (1-based)
                if (flag == patternLength)
                    return i + 1;
            }
        }

        // If pattern not found
        return -1;
    }
}

// Main class to handle user input and run the search
public class NaiveStringSearch {
    public static void main(String[] args) throws IOException {
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input);

        // Read the main text
        System.out.println("Enter the text string:");
        String text = reader.readLine();

        // Read the pattern to search for
        System.out.println("Enter the pattern string:");
        String pattern = reader.readLine();

        // Create object of BruteForceMatcher and perform search
        BruteForceMatcher matcher = new BruteForceMatcher();
        int matchPosition = matcher.bruteForceSearch(text, pattern);

        // Display result
        if (matchPosition != -1)
            System.out.println("Pattern matched at position: " + matchPosition);
        else
            System.out.println("No pattern match found.");
    }
}

Explanation of the Code

bruteForceSearch Method:

Iterates over the text string.
At each position, it compares the pattern with the text starting at that position.
If all characters match, returns the 1-based position.
If no match is found after iterating through the text, returns -1.

Main Program:

Accepts text and pattern input from the user.
Calls the bruteForceSearch method.
Displays whether the pattern is found and its position.

Sample Output

Enter the text string:
what is your name
Enter the pattern string:
is
Pattern matched at position: 6

Explanation of Output

The program takes "what is your name" as the text and "is" as the pattern to search for.

It starts checking the text one character at a time:

At position 1 ('w') → no match with 'i'
At position 2 ('h') → no match
At position 3 ('a') → no match
At position 4 ('t') → no match
At position 5 (' ') → no match
At position 6 ('i') → matches the first character of pattern
- Next character at position 7 ('s') → matches second character of pattern

Since both characters of the pattern match consecutively in the text starting at position 6, the program returns 6 as the match position (using 1-based indexing).

Bottom line is…

The K-Naive (Brute-Force) algorithm is easy to understand and implement for basic string matching tasks. However, it is less efficient for large inputs, where optimized algorithms like KMP or Boyer-Moore are preferable.

@ankurm