修改Boyer Moore以进行多种模式搜索

2 回答

• 0

  我知道了 . 当它在文本中找到模式时，跳过始终为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);
      }
  }
  

  回复于 2024-04-25T14:06:08+08:00
• 5

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

  回复于 2024-04-25T14:06:08+08:00