Хотя существует наиболее эффективный алгоритм сопоставления строковых шаблонов «Knuth-Morris-Pratt». Я пытался добиться того же результата другим подходом. Но я не уверен в его эффективности. Я новичок в программировании. Может ли кто-нибудь показать мне, как проанализировать этот алгоритм и определить его эффективность?

Алгоритм:

Шаг 1. Вычислите целочисленное значение шаблона, добавив целочисленные значения каждого из символов в нем. Пусть будет «м»

Шаг 2: Вычислите целочисленные значения частей строки той же длины, что и образец, аналогично тому, как описано в шаге 1.

Шаг 3. Сохраните эти значения в массиве.

Шаг 4: Сравните значения в массиве со значением «m» из шага 1.

Шаг 5: Если значения совпадают, проверьте, совпадает ли часть строки с шаблоном. Если это так, верните true. Если шаблон не совпадает, верните false.

Я написал алгоритм на Java. Вот код.

public class StringPatternMatchingAlgorithm {
    public static boolean patternMatching(String str,String pattern){
        int patternLength = pattern.length();
        int patternSum = 0;
        int[] patternSumArray = new int[(str.length() - patternLength)+1];
        int patternSumArrayIndex = 0;
        int patternSumToCheck = 0;
        String toCompare = "";
        for(int i=0; i<pattern.length();i++){
            patternSumToCheck = patternSumToCheck + pattern.charAt(i);
            
        }
        for(int i=0; i<((str.length())-(pattern.length()-1));i++){
            patternSum = 0;
            for(int j=i; j<patternLength;j++){
               patternSum = patternSum + str.charAt(j);
            }
            patternLength++;
            patternSumArray[patternSumArrayIndex] = patternSum;
            if(patternSumArrayIndex < patternSumArray.length-1 ){
                patternSumArrayIndex++;
            }    
        }
        for(int i=0; i<patternSumArray.length;i++){
            if(patternSumArray[i] == patternSumToCheck){
                toCompare = "";
               for(int j=i; j<(i+pattern.length());j++){
                   toCompare = toCompare + str.charAt(j);
               }
               if(toCompare.equals(pattern)){
                  return true; 
               }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        String str = "cdxabie";
        String pattern = "bie";
        System.out.println(patternMatching(str, pattern));
    }
 }

Код можно запустить здесь

Редактировать:
Как было сказано в комментариях к первой версии алгоритма, я внес изменения. Я использовал две переменные «forwardIndex» который инициализируется длиной шаблона и «backIndex» инициализировано значением 0. Кроме того, я вычислил целую сумму количества символов, равную длине шаблона из индекса 0, и сохранил ее в переменной с именем «patternSum» только однажды. Затем алгоритм добавляет целое значение символа в «forwardIndex» к «patternSum» и вычитает целое значение символа из «backIndex» из «patternSum» одновременно с перемещением по струне. Это исключает пересчет целой суммы символов в строке, как это было в предыдущей версии алгоритма.

Вот улучшенный код:

public class StringPatternMatchingAlgoVariant1 {

public static boolean matchPattern(String str,String pattern){
    int patternLength = pattern.length();
    int patternSum = 0;
    int[] patternSumArray = new int[(str.length() - patternLength)+1];
    int patternSumArrayIndex = 0;
    int patternSumToCheck = 0;
    String toCompare = "";
    int backIndex = 0;
    int forthIndex = pattern.length();
    for(int i=0; i<pattern.length();i++){
        patternSumToCheck = patternSumToCheck + pattern.charAt(i);
        patternSum = patternSum + str.charAt(i);            
    }
    patternSumArray[patternSumArrayIndex] = patternSum;
    patternSumArrayIndex++;
    for(int i=0; forthIndex<str.length();i++){
        patternSum = patternSum + str.charAt(forthIndex) - str.charAt(backIndex);            
        forthIndex++;
        backIndex++;
        patternSumArray[patternSumArrayIndex] = patternSum;
        patternSumArrayIndex++;             
    }
    for(int i=0; i<patternSumArray.length;i++){
        if(patternSumArray[i] == patternSumToCheck){
            toCompare = "";
           for(int j=i; j<(i+pattern.length());j++){
               toCompare = toCompare + str.charAt(j);
           }
           if(toCompare.equals(pattern)){
              return true; 
           }
        }
    }
    return false;
}
public static void main(String[] args) {
    String str = "cdxabie";
    String pattern = "bie";
    System.out.println(matchPattern(str, pattern));
}  

}

Новую версию кода можно запускать здесь

Пара комментариев к вашему ответу:

Код стиля

• Если вы уже сохранили pattern.length(), зачем продолжать вызывать метод? Просто будьте последовательны и используйте эту переменную. То же самое касается str.length(). Я бы просто сохранил это и использовал.

• Я бы сохранил str.length()-(pattern.length()-1 в переменной имя это что-то вроде numOfCasesToTest, чтобы было понятнее.

• Проверьте использование скобок:

for(int i=0; i<((str.length())-(pattern.length()-1));i++){

Может быть записано как:

for(int i = 0; i < str.length() - pattern.length() - 1; i++){

Излишние скобки затрудняют чтение кода. Подробнее см. Приоритет оператора.

• Сохраняйте постоянный интервал. Хотя некоторые люди предпочитают не иметь пробелов между некоторыми или большинством операторов, я бы предпочел их, так как я думаю, что это делает код более читабельным. Какой бы способ вы ни предпочли, просто продолжайте последовательное использование в коде. Например:

i<patternSumArray.length // no space around comparison operator
patternSumArray[i] == patternSumToCheck // space around comparison operator

Алгоритм

Все это было связано со стилем кода. Теперь комментарий к вашему алгоритму: зачем вычислять сумму всех возможных случаев и только после этого искать совпадение? Таким образом, вы выполняете итерацию по всей str, хотя в этом может быть нет необходимости.

Я вижу, как вы могли прийти к такому решению: вы думали, что процесс был таким, как описано в алгоритме. Но вы можете просто опустить часть, в которой вы храните суммы, и сразу сравнить с совпадением.

Например, предположим, что у вас есть такая строка, как

Abcsomelongstringwithlotsofconentinit

И вы ищете выкройку Abc. Тогда зачем делать все эти вычисления? Просто после того, как вы вычислите одну из этих сумм, сравните ее с суммой шаблона.

Тем не менее (возможно, я наивен), но я не вижу, как вычислить сумму, сравнить ее, а затем фактически сравнить символы лучше, чем просто сравнение символов в первую очередь