Naive String Matching in Java

This is a java program to perform Naive String matching algorithm.

Here is the source code of the Java Program to Perform Naive String Matching. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
 
```
```
package com.sanfoundry.setandstring;
```
```
 
```
```
import java.util.Scanner;
```
```
 
```

public class StringSearchUsingNaiveMethod

```
{
```
```
    private final int BASE;
```
```
    private int[]     occurrence;
```
```
    private String    pattern;
```
```
 
```

    public StringSearchUsingNaiveMethod(String pattern)

```
    {
```
```
        this.BASE = 256;
```
```
        this.pattern = pattern;
```
```
        occurrence = new int[BASE];
```
```
        for (int c = 0; c < BASE; c++)
```
```
            occurrence[c] = -1;
```

        for (int j = 0; j < pattern.length(); j++)

            occurrence[pattern.charAt(j)] = j;

```
    }
```
```
 
```
```
    public int search(String text)
```
```
    {
```
```
        int n = text.length();
```
```
        int m = pattern.length();
```
```
        int skip;
```

        for (int i = 0; i <= n - m; i += skip)

```
        {
```
```
            skip = 0;
```

            for (int j = m - 1; j >= 0; j--)

```
            {
```

                if (pattern.charAt(j) != text.charAt(i + j))

```
                {
```

                    skip = Math.max(1, j - occurrence[text.charAt(i + j)]);

```
                    break;
```
```
                }
```
```
            }
```
```
            if (skip == 0)
```
```
                return i;
```
```
        }
```
```
        return n;
```
```
    }
```
```
 
```

    public static void main(String[] args)

```
    {
```

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter the main string: ");

```
        String text = sc.nextLine();
```

        System.out.print("Enter the string to be searched: ");

```
        String pattern = sc.nextLine();
```

        StringSearchUsingNaiveMethod nsm = new StringSearchUsingNaiveMethod(

```
                pattern);
```

        int first_occur_position = nsm.search(text);

        System.out.println("The text '" + pattern

                + "' is first found after the " + first_occur_position

```
                + " position.");
```
```
        sc.close();
```
```
    }
```
```
}
```

Output:

$ javac StringSearchUsingNaiveMethod.java
$ java StringSearchUsingNaiveMethod
 
Enter the main string: Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel & Device Driver Programming. Our Founder has trained employees of almost all Top Companies in India. Here are few of them: VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium Networks, ST Microelectronics, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Northwest Bank, Mphasis, Tata Elxsi, Tata Communications, Mindtree, Cognizant, mid size IT companies and many Startups. Students from top Universities and colleges such as NIT Trichy, BITS Pilani, University of California, Irvine, University of Texas, Austin & PESIT Bangalore have benefited a lot from these courses as well. The assignments and real time projects for our courses are of extremely high quality with excellent learning curve.
Enter the string to be searched: No. 1 
The text 'No. 1 ' is first found after the 14 position.

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Perform Finite State Automaton based Search

» Next - Java Program to Implement Grep, Egrep and Fgrep Commands

Related Posts:

Recommended Articles: