玉 n 個を輪にして通したネックレスがある。 玉にはそれぞれ英小文字が一つ刻まれていて、ネックレスの文字列 S の i 文字目が i 番目の玉である。 輪になったネックレスなので、n 番目の玉の次にはまた 1 番目の玉が来る。 ネックレスから連続した玉をいくつか切り取って、文字列 T にある文字を T に出てくる個数以上ずつすべて手に入れたい。 切り取る玉はある玉から始まって番号が大きくなる向き（n 番目の次は 1 番目）に続く玉で、同じ玉を二度使うことはできない。 切り取る玉の数をできるだけ少なくせよ。 そのような方法がいくつもあれば、始まる玉の番号が最も小さいものを選ぶ。 始まる玉の番号と切り取る玉の数を、空白で区切って一行に出力せよ。 どう切っても無理なら -1 を出力する。
入力
一行目に S、二行目に T が与えられる。 どちらも英小文字だけからなる文字列である。 1 ≤ S の長さ n ≤ 100,000、1 ≤ T の長さ ≤ 100,000
import syslines = sys.stdin.read().split()s, t = lines[0], lines[1]n = len(s)need = [0] * 26 # 글자마다 더 있어야 하는 수for ch in t: need[ord(ch) - 97] += 1missing = len(t) # 창 안에서 아직 모자란 구슬 수(모두 더한 것)best_start, best_len = -1, n + 1left = 0# 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다)for right in range(2 * n - 1): c = ord(s[right % n]) - 97 if need[c] > 0: missing -= 1 need[c] -= 1 if right - left + 1 > n: # 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 d = ord(s[left % n]) - 97 need[d] += 1 if need[d] > 0: missing += 1 left += 1 if missing == 0: # 왼쪽 끝 구슬이 남아도는 동안 줄인다 while need[ord(s[left % n]) - 97] < 0: need[ord(s[left % n]) - 97] += 1 left += 1 if left < n and right - left + 1 < best_len: # 같은 길이면 먼저 찾은(시작이 앞선) 것 best_start, best_len = left, right - left + 1print(f"{best_start + 1} {best_len}" if best_start >= 0 else -1)
JavaScriptmain.js · 27 行
const [s, t] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const n = s.length;const code = (i) => s.charCodeAt(i % n) - 97; // 두 바퀴 붙인 줄의 i번째 구슬(0~25)const need = new Array(26).fill(0); // 글자마다 더 있어야 하는 수for (const ch of t) need[ch.charCodeAt(0) - 97]++;let missing = t.length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)let bestStart = -1, bestLen = n + 1;let left = 0;for (let right = 0; right < 2 * n - 1; right++) { const c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 const d = code(left++); if (++need[d] > 0) missing++; } if (missing === 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } }}console.log(bestStart >= 0 ? `${bestStart + 1} ${bestLen}` : "-1");
TypeScriptmain.ts · 29 行
import { readFileSync } from "node:fs";const [s, t] = readFileSync(0, "utf8").trim().split(/\s+/);const n = s.length;const code = (i: number): number => s.charCodeAt(i % n) - 97; // 두 바퀴 붙인 줄의 i번째 구슬(0~25)const need: number[] = new Array<number>(26).fill(0); // 글자마다 더 있어야 하는 수for (const ch of t) need[ch.charCodeAt(0) - 97]++;let missing = t.length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)let bestStart = -1, bestLen = n + 1;let left = 0;for (let right = 0; right < 2 * n - 1; right++) { const c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 const d = code(left++); if (++need[d] > 0) missing++; } if (missing === 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } }}console.log(bestStart >= 0 ? `${bestStart + 1} ${bestLen}` : "-1");
JavaMain.java · 41 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); String t = in.readLine().trim(); int n = s.length(); int[] need = new int[26]; // 글자마다 더 있어야 하는 수 for (char ch : t.toCharArray()) need[ch - 'a']++; int missing = t.length(); // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; // 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) for (int right = 0; right < 2 * n - 1; right++) { int c = s.charAt(right % n) - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 int d = s.charAt(left % n) - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s.charAt(left % n) - 'a'] < 0) { // 왼쪽 끝 구슬이 남아도는 동안 줄인다 need[s.charAt(left % n) - 'a']++; left++; } if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } } } System.out.println(bestStart >= 0 ? (bestStart + 1) + " " + bestLen : "-1"); }}
C#Main.cs · 45 行
using System;class Program{ static void Main() { string s = Console.ReadLine().Trim(); string t = Console.ReadLine().Trim(); int n = s.Length; var need = new int[26]; // 글자마다 더 있어야 하는 수 foreach (char ch in t) need[ch - 'a']++; int missing = t.Length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; // 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) for (int right = 0; right < 2 * n - 1; right++) { int c = s[right % n] - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 { int d = s[left % n] - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s[left % n] - 'a'] < 0) // 왼쪽 끝 구슬이 남아도는 동안 줄인다 { need[s[left % n] - 'a']++; left++; } if (left < n && right - left + 1 < bestLen) // 같은 길이면 먼저 찾은(시작이 앞선) 것 { bestStart = left; bestLen = right - left + 1; } } } Console.WriteLine(bestStart >= 0 ? $"{bestStart + 1} {bestLen}" : "-1"); }}
C++main.cpp · 37 行
#include <array>#include <iostream>#include <string>int main() { std::string s, t; std::cin >> s >> t; const int n = static_cast<int>(s.size()); auto code = [&](int i) { return s[i % n] - 'a'; }; // 두 바퀴 붙인 줄의 i번째 구슬(0~25) std::array<int, 26> need{}; // 글자마다 더 있어야 하는 수 for (char ch : t) need[ch - 'a']++; int missing = static_cast<int>(t.size()); // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; for (int right = 0; right < 2 * n - 1; right++) { int c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 int d = code(left++); if (++need[d] > 0) missing++; } if (missing == 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } } } if (bestStart >= 0) std::cout << bestStart + 1 << " " << bestLen << "\n"; else std::cout << -1 << "\n";}
Cmain.c · 44 行
#include <stdio.h>#include <string.h>#define MAXL 100000static char s[MAXL + 2], t[MAXL + 2];int main(void) { scanf("%100001s %100001s", s, t); int n = (int)strlen(s), k = (int)strlen(t); int need[26] = {0}; /* 글자마다 더 있어야 하는 수 */ for (int i = 0; i < k; i++) need[t[i] - 'a']++; int missing = k; /* 창 안에서 아직 모자란 구슬 수(모두 더한 것) */ int best_start = -1, best_len = n + 1; int left = 0; /* 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) */ for (int right = 0; right < 2 * n - 1; right++) { int c = s[right % n] - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { /* 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 */ int d = s[left % n] - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s[left % n] - 'a'] < 0) { /* 왼쪽 끝 구슬이 남아도는 동안 줄인다 */ need[s[left % n] - 'a']++; left++; } if (left < n && right - left + 1 < best_len) { /* 같은 길이면 먼저 찾은(시작이 앞선) 것 */ best_start = left; best_len = right - left + 1; } } } if (best_start >= 0) printf("%d %d\n", best_start + 1, best_len); else puts("-1"); return 0;}
Craykonmain.cray · 60 行
// 두 바퀴 붙인 줄의 i번째 구슬을 0~25 번호로구슬(s, i){ 返す 文字.コード(s[i % s.長さ]) - 97;}s = コンソール.行読み().空白除去();t = コンソール.行読み().空白除去();n = s.長さ;need = 新リスト(26, 0); // 글자마다 더 있어야 하는 수それぞれ (ch の中 t){ need[文字.コード(ch) - 97] += 1;}missing = t.長さ; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)bestStart = -1;bestLen = n + 1;left = 0;繰り返す (right = 0; right < 2 * n - 1; right++){ c = 구슬(s, right); もし (need[c] > 0) { missing -= 1; } need[c] -= 1; もし (right - left + 1 > n) { d = 구슬(s, left); left += 1; need[d] += 1; もし (need[d] > 0) { missing += 1; } } もし (missing == 0) { 間 (need[구슬(s, left)] < 0) { need[구슬(s, left)] += 1; left += 1; } もし (left < n && right - left + 1 < bestLen) { bestStart = left; bestLen = right - left + 1; } }}もし (bestStart >= 0){ コンソール.書く(bestStart + 1 + " " + bestLen);}でなければ{ コンソール.書く(-1);}