algorithm
Алгоритм Кнут Моррис Пратт (KMP)
Поиск…
Вступление
KMP - это алгоритм сопоставления с образцом, который ищет появление «слова» W в основной «текстовой строке» S , используя наблюдение, что, когда происходит несоответствие, мы располагаем достаточной информацией, чтобы определить, где можно начать следующее совпадение. Мы используйте эту информацию, чтобы избежать совпадения символов, которые, как мы знаем, будут в любом случае соответствовать. Самая сложная сложность поиска шаблона сводится к O (n) .
КМР-пример
Алгоритм
Этот алгоритм является двухэтапным процессом. Сначала мы создаем вспомогательный массив lps [], а затем используем этот массив для поиска шаблона.
Предварительная обработка :
- Мы предварительно обрабатываем шаблон и создаем вспомогательный массив lps [], который используется для пропуска символов при совпадении.
- Здесь lps [] указывает на самый длинный правильный префикс, который также является суффиксом. Правильный префикс является префиксом, в котором целая строка не включена. Например, префиксы строки ABC - это «» , «A» , «AB» и «ABC» . Правильными префиксами являются «» , «A» и «AB» . Суффиксами строки являются «» , «C» , «BC» и «ABC» .
поиск
Мы сохраняем соответствующие символы txt [i] и pat [j] и продолжаем увеличивать i и j, пока pat [j] и txt [i] сохраняют соответствие.
Когда мы видим несоответствие, мы знаем, что символы pat [0..j-1] соответствуют txt [i-j + 1 ... i-1]. Мы также знаем, что lps [j-1] - количество символов pat [0 ... j-1], которые являются как правильным префиксом, так и суффиксом. Из этого можно заключить, что нам не нужно сопоставлять эти lps [j-1] символы с txt [ij ... i-1], потому что мы знаем, что эти символы будет соответствовать в любом случае.
Реализация в Java
public class KMP {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "abcabdabc";
String pattern = "abc";
KMP obj = new KMP();
System.out.println(obj.patternExistKMP(str.toCharArray(), pattern.toCharArray()));
}
public int[] computeLPS(char[] str){
int lps[] = new int[str.length];
lps[0] = 0;
int j = 0;
for(int i =1;i<str.length;i++){
if(str[j] == str[i]){
lps[i] = j+1;
j++;
i++;
}else{
if(j!=0){
j = lps[j-1];
}else{
lps[i] = j+1;
i++;
}
}
}
return lps;
}
public boolean patternExistKMP(char[] text,char[] pat){
int[] lps = computeLPS(pat);
int i=0,j=0;
while(i<text.length && j<pat.length){
if(text[i] == pat[j]){
i++;
j++;
}else{
if(j!=0){
j = lps[j-1];
}else{
i++;
}
}
}
if(j==pat.length)
return true;
return false;
}
}