#include using namespace std; const int N = 1000010; int n, m, ne[N]; char s[N], p[N]; int main() { #ifndef ONLINE_JUDGE freopen("P3375.in", "r", stdin); #endif cin >> (s + 1) >> (p + 1); // 先长串,再短串 n = strlen(p + 1), m = strlen(s + 1); // 自已来测长 // 求模式串ne数组 for (int i = 2, j = 0; i <= n; i++) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j++; ne[i] = j; } // 求源串中模式串出现的每个位置 for (int i = 1, j = 0; i <= m; i++) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j++; if (j == n) { printf("%d\n", i - n + 1); j = ne[j]; // 继续搜索,重置 j=ne[j] } } // 本题要求最后输出模式串的ne数组 for (int i = 1; i <= n; i++) cout << ne[i] << " "; return 0; }