#include #include #include // Meze #define MAXJ 52 #define MAXS 2000000 // Trik: Jak jehlu, tak seno indexujeme od 1. Před i za řetězcem je vždy znak 0. int J, S; char jehla[MAXJ+2]; char seno[MAXS+2]; // Předpočítané proměnné (0 vždy značí "nedefinováno") int znak[256]; // Převod kódu znaku na pořadové číslo v jehle (znak[jehla[j]] == j) int prvni[MAXJ+2]; // prvni[j] je pozice prvního výskytu j-tého znaku jehly v seně int dalsi[MAXS+1]; // dalsi[i] je pozice dalšího výskytu znaku seno[i] int skok[MAXS+1]; // Je-li seno[i] výskyt jehla[j], seno[skok[i]] je nejbližší // další výskyt jehla[j+1]. // Pozice aktuálního výskytu jehly int nalezeno[MAXJ+1]; // Prohledávání do hloubky pomocí předpočítaných hodnot void dfs(int j, int i) { if (j > J) { for (int k=1; k<=J; k++) printf("%d%c", nalezeno[k], (k < J ? ' ' : '\n')); return; } while (i) { nalezeno[j] = i; dfs(j+1, skok[i]); i = dalsi[i]; } } int main(void) { // Čtení vstupu a výpočet znak[] scanf("%d%s%d%s", &S, seno+1, &J, jehla+1); for (int j=1; j<=J; j++) znak[jehla[j]] = j; // Předvýpočet ostatních polí for (int i=S; i>=1; i--) { int j = znak[seno[i]]; if (j && (j == J || prvni[j+1])) { dalsi[i] = prvni[j]; prvni[j] = i; skok[i] = prvni[j+1]; } } // Rekurze! Hrrr na ně! dfs(1, prvni[1]); return 0; }