#include <stdio.h> #include <string.h> #include <stdlib.h>#define MAX_TEXT_LEN 1000005 #define MAX_PATTERN_LEN 100005char text[MAX_TEXT_LEN]; char pattern[MAX_PATTERN_LEN]; int next[MAX_PATTERN_LEN];void buildNext(char *p, int m) {int j = 0;next[0] = 0;for (int i = 1; i < m; i++) {while (j > 0 && p[i] != p[j]) {j = next[j - 1];}if (p[i] == p[j]) {j++;}next[i] = j;} }char* kmpSearch(char *t, int n, char *p, int m) {if (m == 0) return NULL;buildNext(p, m);int j = 0;for (int i = 0; i < n; i++) {while (j > 0 && t[i] != p[j]) {j = next[j - 1];}if (t[i] == p[j]) {j++;}if (j == m) {return &t[i - m + 1];}}return NULL; }int main() {if (scanf("%s", text) != 1) return 0;int n_len = strlen(text);int n;if (scanf("%d", &n) != 1) return 0;while (n--) {scanf("%s", pattern);int m_len = strlen(pattern);if (m_len > n_len) {printf("Not Found\n");continue;}char *result = kmpSearch(text, n_len, pattern, m_len);if (result != NULL) {printf("%s\n", result);} else {printf("Not Found\n");}}return 0; }