2
\$\begingroup\$

I am trying to solve a string matching question mentioned here. I recently learned the Knuth–Morris–Pratt algorithm and tried to implement it to solve this question. But I am getting a TLE for this code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Gogl {
    static int count=0;
    public static void main(String[] args) 
    {
        MyScannergogl sc=new MyScannergogl();//used own input function
        String text=sc.next();
        String pattern=sc.next();
        KMP(text,pattern);

            System.out.println(count);



    }
    static int[] computeTempArray(String pattern)
    {
        int lsp[]=new int[pattern.length()];
        int index=0;
        int i;
        for(i=1;i<pattern.length();)
        {
            if(pattern.charAt(i)==pattern.charAt(index))
            {
                lsp[i]=lsp[index]+1;
                i++;
                index++;
            }
            else
            {
                if(index!=0)
                {
                    index=lsp[i-1];
                }
                else
                {
                    lsp[i]=0;
                    i++;
                }
            }
        }
        return lsp;
    }
    public static void KMP(String text,String pat)
    {
        int lsp[]=computeTempArray(pat);
        int i=0;
        int j=0;
        while(i<text.length() )
        {

            if(text.charAt(i)==pat.charAt(j))
            {
                i++;
                j++;
            }
            else
            {
                if(j!=0)
                {
                    j=lsp[j-1];
                }
                else
                {
                    i++;
                }
            }
            if(j==pat.length())
            {
                count++;
                j=0;
            }
        }

    }

}

I couldn't understand where am I wrong. Whether I have not properly implemented the algorithm or is there some other problem I am not aware of. As I know that KNP is really fast so should have crossed the time limit.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
    int i;
    for(i=1;i<pattern.length();)
    {
        if(pattern.charAt(i)==pattern.charAt(index))
        {
            lsp[i]=lsp[index]+1;
            i++;
            index++;
        }
        else
        {
            if(index!=0)
            {
                index=lsp[i-1];
            }
            else
            {
                lsp[i]=0;
                i++;
            }
        }
    }

That's a while loop. There's no need to use for here.

    int i = 1;
    while(i<pattern.length())
    {
        if(pattern.charAt(i)==pattern.charAt(index))
        {
            lsp[i]=lsp[index]+1;
            i++;
            index++;
        }
        else
        {
            if(index!=0)
            {
                index=lsp[i-1];
            }
            else
            {
                lsp[i]=0;
                i++;
            }
        }
    }

You might want to use more descriptive variables in your code, because I have the hardest time trying to understand what lsp is. The i and j variables aren't helping either: are you traversing two collections? In what way?

Your class names are weird, what does Gogl mean?

More descriptive variables and classnames will help you when you view your code at a later point in time. If you don't feel like explaining the algorithm in code, at least put the name of the algorithm together with a link as a comment in the code.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.