#include <iostream>
#include <string>
#include <vector>
//test chatgpt
using namespace std;

// 预处理 next 数组
vector<int> getNext(const string& pattern) {
  int m = pattern.length();
  vector<int> next(m, 0); // 初始化 next 数组为 0
  int j = 0;
  for (int i = 1; i < m; i++) {
    // 如果 pattern[i] 不匹配，则 j 回退到 next[j-1]
    while (j > 0 && pattern[i] != pattern[j]) {
      j = next[j - 1];
    }
    if (pattern[i] == pattern[j]) {
      // 如果匹配，j 加一
      j++;
    }
    next[i] = j;
  }
  return next;
}

int main() {
  string text, pattern;
  cin >> text >> pattern;
  int n = text.length();
  int m = pattern.length();
  vector<int> next = getNext(pattern);
  int j = 0;
  for (int i = 0; i < n; i++) {
    // 如果 text[i] 不匹配，则 j 回退到 next[j-1]
    while (j > 0 && text[i] != pattern[j]) {
      j = next[j - 1];
    }
    if (text[i] == pattern[j]) {
      // 如果匹配，j 加一
      j++;
    }
    if (j == m) {
      // 匹配成功，输出结果
      cout << i - m + 2 << endl;
      j = next[j - 1];
    }
  }
  for(auto nxt:next){
      cout<<nxt<<" ";
  }
  return 0;
}

Q:为什么不匹配就要回退到 next[j-1]

ChatGPT:在预处理 next 数组时，如果当前字符 pattern[i] 与前一个字符 pattern[j] 不匹配，则说明在前缀字符串 pattern[0] ~ pattern[j-1] 中没有相同的前后缀字符串，我们不能继续比较下去。此时我们就需要将匹配的指针回退到 next[j-1]，继续向后比较。

因此，回退到 next[j-1] 是为了尽可能多地匹配前缀字符串和后缀字符串，提高匹配的效率。

在 KMP 算法中，通过预处理 next 数组，使得我们可以避免回溯到已经处理过的字符，提高了匹配的效率。

Q:为什么说回退到 next[j-1] 就相当于回到了前一个最长公共前后缀的位置?

ChatGPT:当匹配过程中发现不匹配，回退到 next[j-1] 的目的是查找下一个可能的最长公共前后缀。

因为 next[j-1] 即为当前位置字符的前一个字符对应的最长公共前后缀长度。所以回退到 next[j-1] 就相当于从当前位置的最长公共前后缀移动到了前一个字符的最长公共前后缀，从而继续匹配。

这么做的原理是：最长公共前后缀长度即为可以在不重复匹配的情况下最多可以向后移动的字符数量，因此可以保证匹配的效率。回退到 next[j-1] 就是为了寻找下一个可能的最长公共前后缀，从而继续提高匹配的效率。