java - Java中允许有一处不匹配的KMP算法

Question

我正在尝试解决 HackerRank challenge ，但我遇到了问题。显然，如果出于性能要求(我尝试过)，O(n^2) 的蛮力解决方案将不会削减，所以我开始寻找更优雅的解决方案。那是我登陆 KMP 的时候。并关注 this tutorial我实现了它。

但是，挑战表明您实际上可以在字符串中有一个不匹配，因此我尝试在我的代码中添加该功能。但是，我得到的结果不正确，我完全不知道为什么。有人可以看看我的解决方案并指出正确的方向吗？

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    //This failure function creates an array of integers
    //that indicate if there is a prefix that is both a
    //prefix and a suffix of the word and at what position
    //the prefix ends
  private static int[] failureFunction(char[] p){
    int i = 0;
    int j = -1;
    int len = p.length;
    int[] f = new int[len+1];
    f[i] = j;
    int potentialWrong = 0;
    while(i<len){

      // if(j>=0 && p[i] != p[j]){
      //   potentialWrong++;
      // }

      // if(potentialWrong > 1){
        // potentialWrong = 0;
        while(j>=0 && p[i] != p[j]){
          //if there is a mismatch consider the
          //next widest border. The borders to be
          //examined are obtained in decreasing order
          // from the values f[i], f[f[i]] etc.
          j=f[j];
        }
      // }
      i++;
      j++;
      f[i]=j;
    }
    // for(int k : f){
    //   System.out.print(k+" ");
    // }

    return f;
  }

  private static LinkedList<Integer> searchKMP(char[] text, char[] ptrn){
    int[] b = failureFunction(ptrn);

    int j=0;
    int i=0;
     // pattern and text lengths
    int ptrnLen = ptrn.length;
    int txtLen = text.length;

    int potentialWrong = 0;
    LinkedList<Integer> list = new LinkedList<Integer>();

    while(i<txtLen){
      // System.out.println("i: "+i +", j: " +j);
      if(text[i] != ptrn[j]){
        potentialWrong++;
      }
      System.out.println("txt: " +text[i] +", ptrn: "+ptrn[j]);
      System.out.println("Num wrong: " + potentialWrong);

      if(potentialWrong > 1){
        potentialWrong = 0;
        while (j >= 0 && text[i] != ptrn[j]) {
          j = b[j];
        }
      }

      i++;
      j++;

        // a match is found
      if (j == ptrnLen) {
        list.add(i - ptrnLen);
        j = b[j];
      }
    }
    return list;
  }

//   private static boolean isValidMatch(String maybe, String virus){
//    int numWrong = 0;
//                    // System.out.println(maybe +"vs."+ virus);

//    for(int i=0;i<maybe.length();i++){
//     if(maybe.charAt(i) != virus.charAt(i)){
//       numWrong++;
//     }
//     if(numWrong > 1 ) return false;
//   }

//   return true;
// }

// private static LinkedList<Integer> getMatches(String patient, String virus){
//   LinkedList<Integer> indices = new LinkedList<Integer>();
//   for(int i=0;i<patient.length();i++){
//     if(i+virus.length()-1 < patient.length()){
//       if(isValidMatch(patient.substring(i, i+virus.length()), virus)){
//         indices.add(i);
//       }
//     }
//     else{
//       break;
//     }
//   }

//   return indices;

// }

  public static void main(String[] args) {
    Scanner scn = new Scanner(System.in);
    int T = scn.nextInt();
    String patient;
    String virus;
    for(int i =0;i<T;i++){
    scn.nextLine(); //for empty line
    patient = scn.nextLine();
    virus = scn.nextLine();

    LinkedList<Integer> list = searchKMP(patient.toCharArray(), virus.toCharArray());
    for(int k : list){
      System.out.print(k+" ");
    }

    System.out.println("");
  }
}
}

Answer 1

public class KMPStringSearch {

    /**
     * Searches for all occurances of the word in the sentence. Runs in O(n+k)
     * where n is the word length and k is the sentence length.
     *
     * @param word The word that is being searched
     * @param sentence The collections of word over which the search happens.
     * @return The list of starting indices of the matched word in the sentence.
     * Empty list in case of no match.
     */
    public List<Integer> searchString(final String word, final String sentence) {
        final List<Integer> matchedIndices = new ArrayList<>();

        final int sentenceLength = sentence.length();
        final int wordLength = word.length();
        int beginMatch = 0; // the starting position in sentence from which the match started
        int idxWord = 0; // the index of the character of the word that is being compared to a character in string
        final List<Integer> partialTable = createPartialMatchTable(word);
        while (beginMatch + idxWord < sentenceLength) {
            if (word.charAt(idxWord) == sentence.charAt(beginMatch + idxWord)) {
                // the characters have matched
                if (idxWord == wordLength - 1) {
                    // the word is complete. we have a match.
                    matchedIndices.add(beginMatch);
                    // restart the search
                    beginMatch = beginMatch + idxWord - partialTable.get(idxWord);
                    if (partialTable.get(idxWord) > -1) {
                        idxWord = partialTable.get(idxWord);
                    } else {
                        idxWord = 0;
                    }
                } else {
                    idxWord++;
                }
            } else {
                // mismatch. restart the search.
                beginMatch = beginMatch + idxWord - partialTable.get(idxWord);
                if (partialTable.get(idxWord) > -1) {
                    idxWord = partialTable.get(idxWord);
                } else {
                    idxWord = 0;
                }
            }
        }

        return Collections.unmodifiableList(matchedIndices);
    }

    /**
     * Creates the Partial Match Table for the word. Runs in O(n) where n is the
     * length of the word.
     *
     * @param word The word whose Partial Match Table is required.
     * @return The table as a list of integers.
     */
    public List<Integer> createPartialMatchTable(final String word) {
        if (StringUtils.isBlank(word)) {
            return Collections.EMPTY_LIST;
        }

        final int length = word.length();
        final List<Integer> partialTable = new ArrayList<>(length + 1);
        partialTable.add(-1);
        partialTable.add(0);

        final char firstChar = word.charAt(0);
        for (int idx = 1; idx < word.length(); idx++) {
            final int prevVal = partialTable.get(idx);
            if (prevVal == 0) {
                if (word.charAt(idx) == firstChar) {
                    partialTable.add(1);
                } else {
                    partialTable.add(0);
                }
            } else if (word.charAt(idx) == word.charAt(prevVal)) {
                partialTable.add(prevVal + 1);
            } else {
                partialTable.add(0);
            }
        }

        return Collections.unmodifiableList(partialTable);
    }
}