다중 패턴 검색을위한 Boyer Moore 수정

Question

나는이 site에 따라 Boyer Moore 알고리즘을 사용했습니다. 이것은 한 번만 텍스트의 패턴 검색을 구현하고 프로그램이 종료됩니다. 누구든지 패턴을 시작과 끝 인덱스로 여러 번 찾으려면이 코드를 수정하는 것을 도와 줄 수 있습니까?

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

알았어. 텍스트에서 패턴을 발견하면 스킵은 항상 0이었습니다.

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