#include #include #include #define MAX_INPUT_SIZE 2000001 // Maximální délka sena #define ALPHABET_SIZE 57 // Velikost abecedy #define MAX_J ALPHABET_SIZE // Maximální délka jehly // Vrchol grafu struct vertex { struct vertex *same_in_needle; // Příští výskyt téhož znaku jehly struct vertex *next_in_needle; // Příští výskyt dalšího znaku jehly int position_in_input; // Pozice vrcholu v seně }; struct vertex *leftmost[MAX_J]; // Nejlevější výskyt každého znaku struct vertex vertices[MAX_INPUT_SIZE]; // Pole vrcholů grafu int used_vertices; // Kolik vrcholů jsme už použili int index_in_needle[ALPHABET_SIZE]; // Znak -> pozice v jehle char input[MAX_INPUT_SIZE]; // Seno char needle[MAX_J]; // Jehla int input_length; // Délka sena int needle_length; // Délka jehly int output_buffer[MAX_J]; // Zde si skládáme výstup // Rekurzivní prohledávání grafu void print(struct vertex* vertex, int index) { output_buffer[index] = vertex->position_in_input; if (vertex->next_in_needle == NULL) { for (int i = 1; i <= index; i++) { printf("%d ", output_buffer[i]); } printf("\n"); } else { print(vertex->next_in_needle, index + 1); } if (vertex->same_in_needle != NULL) { print(vertex->same_in_needle, index); } } int main() { // Přečteme vstup scanf("%d", &input_length); scanf("%s", &input[1]); scanf("%d", &needle_length); scanf("%s", &needle[1]); // Překlad písmen na pozici v jehle for (int i = 1; i <= needle_length; i++) { index_in_needle[needle[i] - 'A'] = i; } // Tvorba grafu for (int i = input_length; i > 0; i--) { int index = index_in_needle[input[i] - 'A']; if (index > 0) { int process = index == needle_length || leftmost[index + 1] != NULL; if (process) { struct vertex *vertex = &vertices[used_vertices++]; if (index != needle_length) { vertex->next_in_needle = leftmost[index + 1]; } if (leftmost[index] != NULL) { vertex->same_in_needle = leftmost[index]; } vertex->position_in_input = i; leftmost[index] = vertex; } } } // Prohledání grafu if (leftmost[1] != NULL) { print(leftmost[1], 1); } return 0; }