Почему мой подход на основе KMP не работает для «Самой короткой подборочной подстроки ⇐ C++

[Anonymous]

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

[*] Я разделял шаблон p на три части на основе двух '*' < /code> символы.
[*] Я использую kmp (knuth-morris-pratt algorithm) , чтобы найти вхождения этих трех частей в s .
Затем я пытаюсь найти самую короткую подборинг в s , которая содержит все три части в правильном порядке.
< /ol>
выпуск: < /h3>

• Функция не всегда возвращает правильный ответ. < /li>
  Иногда он возвращает -1 , когда существует действительная подстрока.
• Я подозреваю >
  < /ul>
  Может ли кто -нибудь помочь мне определить, что не так с моим подходом? class = "lang-cpp prettyprint-override">

  Код: Выделить всё

  class Solution {
  public:
  void calculateLPS(string& needle, vector& lps) {
  int m = needle.size();
  lps[0] = 0;
  int len = 0;
  int i = 1;
  while (i < m) {
  if (needle[i] == needle[len]) {
  len++;
  lps[i] = len;
  i++;
  } else {
  if (len != 0) {
  len = lps[len - 1];
  } else {
  lps[i] = 0;
  i++;
  }
  }
  }
  }
  
  vector kmp(string& haystack, string& needle) {
  int m = needle.size();
  int n = haystack.size();
  if (m > n) return {};
  vector lps(m, 0);
  calculateLPS(needle, lps);
  int i = 0, j = 0;
  vector ans;
  while (i < n) {
  if (haystack[i] == needle[j]) {
  i++;
  j++;
  }
  if (j == m) {
  ans.push_back(i - j);
  j = lps[j - 1];
  } else if (i < n && haystack[i] != needle[j]) {
  if (j != 0) {
  j = lps[j - 1];
  } else {
  i++;
  }
  }
  }
  return ans;
  }
  
  int shortestMatchingSubstring(string s, string p) {
  int j = 0;
  vector strs(3, "");
  for (int i = 0; i < p.size(); i++) {
  if (p[i] != '*') {
  strs[j].push_back(p[i]);
  } else if (p[i] == '*') {
  j++;
  }
  }
  
  vector startIdx = kmp(s, strs[0]);
  vector midIdx = kmp(s, strs[1]);
  vector endIdx = kmp(s, strs[2]);
  
  if (startIdx.empty() || endIdx.empty()) return -1;
  int minLength = INT_MAX;
  
  for (int start : startIdx) {
  for (int mid : midIdx) {
  if (mid > start) {
  for (int end : endIdx) {
  if (end > mid) {
  minLength = min(minLength, end + (int)strs[2].size() - start);
  break;
  }
  }
  break;
  }
  }
  }
  
  return (minLength == INT_MAX) ? -1 : minLength;
  }
  };
  < /code>
   ожидаемое поведение: < /h3>
  
   Функция должна вернуть длину самой короткой подстроки < /strong> в s 

  , который соответствует p с учетом '*' как подстановочный знак. . < /li>
  < /ul>
  Пример тестового примера: < /h3>

  Код: Выделить всё

  string s = "abaacbaecebce";
  string p = "ba*c*ce";
  Solution sol;
  cout 
   [b] Я правильно обращаюсь с показателями при проверке самой короткой подстроки? < /strong> < /li>
   Отсутствует? [/b]
  [/list] 
  
  Подробнее здесь: [url]https://stackoverflow.com/questions/79442796/why-is-my-kmp-based-approach-not-working-for-shortest-matching-substring[/url]