Modifying Boyer Moore for multiple pattern search

Question

I have used Boyer Moore algorithm according to this site. This implements pattern search in the text for only once and the program exits. Can anyone help me to modify this code in order to find the pattern multiple times with their starting and ending index?

    public class BoyerMoore {
        private final int R;     // the radix
        private int[] right;     // the bad-character skip array
        private String pat;      // or as a string

        // pattern provided as a string
        public BoyerMoore(String pat) {
            this.R = 256;
            this.pat = pat;

            // position of rightmost occurrence of c in the pattern
            right = new int[R];
            for (int c = 0; c < R; c++)
                right[c] = -1;
            for (int j = 0; j < pat.length(); j++)
                right[pat.charAt(j)] = j;
        }

        // return offset of first match; N if no match
        public ArrayList<Integer> search(String txt) {
            int M = pat.length();
            int N = txt.length();
            ArrayList<Integer> newArrayInt = new ArrayList<Integer>();
            int skip;
            for (int i = 0; i <= N - M; i += skip) {
                skip = 0;
                for (int j = M-1; j >= 0; j--) {
                    if (pat.charAt(j) != txt.charAt(i+j)) {
                        skip = Math.max(1, j - right[txt.charAt(i+j)]);
                        break;
                    }
                }
                if (skip == 0) 
                    newArrayInt.add(i);    // found
            }
            return newArrayInt;                       // not found
        }

        // test client
        public static void main(String[] args) {
            String pat = "abc";
            String txt = "asdf ghjk klll abc qwerty abc and poaslf abc";

            BoyerMoore boyermoore1 = new BoyerMoore(pat);

            ArrayList<Integer> offset = boyermoore1.search(txt);

            // print results
            System.out.println("Offset: "+ offset);


 }
}

Answer 1

I got it. The skip was always 0 when it found the pattern in the text.

public class BoyerMoore {
    private final int R;     // the radix
    private int[] right;     // the bad-character skip array
    private String pat;      // or as a string

    // pattern provided as a string
    public BoyerMoore(String pat) {
        this.R = 256;
        this.pat = pat;

        // position of rightmost occurrence of c in the pattern
        right = new int[R];
        for (int c = 0; c < R; c++)
            right[c] = -1;
        for (int j = 0; j < pat.length(); j++)
            right[pat.charAt(j)] = j;
    }

    // return offset of first match; N if no match
    public ArrayList<Integer> search(String txt) {
        int M = pat.length();
        int N = txt.length();
        ArrayList<Integer> newArrayInt = new ArrayList<Integer>();
        int skip;
        for (int i = 0; i <= N - M; i += skip) {
            skip = 0;
            for (int j = M-1; j >= 0; j--) {
                if (pat.charAt(j) != txt.charAt(i+j)) {
                    skip = Math.max(1, j - right[txt.charAt(i+j)]);
                    break;
                }
            }
            if (skip == 0) 
            {
                newArrayInt.add(i);    // found
                skip++;
            }
        }
        return newArrayInt;                       // not found
    }

    // test client
    public static void main(String[] args) {
        String pat = "abc";
        String txt = "asdf ghjk klll abc qwerty abc and poaslf abc";

        BoyerMoore boyermoore1 = new BoyerMoore(pat);

        ArrayList<Integer> offset = boyermoore1.search(txt);

        // print results
        System.out.println("Offset: "+ offset);
    }
}

Answer 2

public class Boyer {
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner get= new Scanner(System.in);
      String m,n;
      int i,j;
      String T,P;
      T=get.nextLine();
      System.out.println("Text T is"+T);
      P=get.nextLine();
      System.out.println("Pattern P is"+P);
      int n1=T.length();
      int m1=P.length();
      for(i=0;i<=n1-m1;i++){
           j=0;
          while(j<m1 && (T.charAt(i+j)==P.charAt(j))){
               j=j+1;
               if(j==m1)
                   System.out.println("match found at"+i);
          }
      }
    }
}