#include #define MAXN 1000 #define MAXK 1000 typedef struct { int pocty[30]; } tice; int stejne_pocty (tice *a, tice *b) /* Vrátí 1 pokud |a| a |b| jsou stejné. */ { unsigned i; for (i = 0; i < 30; i++) if (a->pocty[i] != b->pocty[i]) return 0; return 1; } void casesort (tice *to_sort[], unsigned l, unsigned k, unsigned slozka) /* Setřídí |L| 30-tic v |to_sort| podle |složky|. */ { tice *tmp[MAXN]; unsigned case_size[MAXK + 1]; unsigned case_begin[MAXK + 1]; unsigned i; for (i = 0; i <= k; i++) case_size[i] = 0; for (i = 0; i < l; i++) case_size[to_sort[i]->pocty[slozka]]++; case_begin[0] = 0; for (i = 1; i <= k; i++) case_begin[i] = case_begin[i - 1] + case_size[i - 1]; for (i = 0; i < l; i++) tmp[case_begin[to_sort[i]->pocty[slozka]]++] = to_sort[i]; for (i = 0; i < l; i++) to_sort[i] = tmp[i]; } void radixsort (tice *to_sort[], unsigned l, unsigned k) /* Setřídí lexikograficky |l| 30-tic v poli |to_sort|.*/ { int i; for (i = 29; i >= 0; i--) casesort (to_sort, l, k, i); } unsigned kod(char ch) /* Vrátí kód znaku |ch|. */ { if ('a' <= ch && ch <= 'z') return ch - 'a'; if ('A' <= ch && ch <= 'Z') return ch - 'A'; if (ch == '_') return 'z' - 'a' + 1; if (ch == '.') return 'z' - 'a' + 2; if (ch == '?') return 'z' - 'a' + 3; if (ch == '!') return 'z' - 'a' + 4; abort (); } int main(void) { char vstup[MAXN + 1]; tice T[MAXN]; tice *T_sorted[MAXN]; unsigned n, k; unsigned i, p; unsigned min_opak; scanf ("%d%d%s", &n, &k, vstup); memset (&T[0], 0, sizeof (tice)); for (i = 0; i < k; i++) /* Spočítáme četnosti písmen v k-ticích. */ T[0].pocty[kod (vstup[i])]++; for (; i < n; i++) { p = i - k + 1; T[p] = T[p-1]; T[p].pocty[kod (vstup[i])]++; T[p].pocty[kod (vstup[p - 1])]--; } for (i = 0; i < n - k + 1; i++) /* Setřídíme 30-tice. */ T_sorted[i] = &T[i]; radixsort (T_sorted, n - k + 1, k); min_opak = n; for (i = 1; i < n - k + 1; i++) /* A najdeme první opakující se. */ if (stejne_pocty (T_sorted[i], T_sorted[i - 1])) { p = T_sorted[i] - T; if (p < min_opak) min_opak = p; } if (min_opak == n) printf ("Žádné opakování.\n"); else printf ("Žádné opakování do pozice %d.\n", min_opak + k - 1); return 0; }