有一条把 n 颗珠子串成一圈的项链。
每颗珠子上刻着一个小写英文字母，项链字符串 S 的第 i 个字符就是第 i 颗珠子。
因为项链是圆的，第 n 颗珠子后面又是第 1 颗珠子。
要从项链上剪下连续的若干颗珠子，使得字符串 T 中的每个字母都至少拥有它在 T 中出现的次数。
剪下的珠子从某一颗开始沿编号增大的方向（第 n 颗之后是第 1 颗）连续，同一颗珠子不能用两次。
让剪下的珠子数尽可能少。
如果有多种方法，选起始珠子编号最小的。
把起始珠子的编号和剪下的珠子数用空格分隔输出在一行。
怎么剪都不行时输出 -1。
cabbad dc
6 2
ab aa
-1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
用双指针（滑动窗口）来解：右端一个一个向右扩，同时减少每个字母"还需要的数"（need）；当没有缺的珠子时（missing == 0），只要左端的珠子是多余的就把左端往右收。
两端都只向前走，所以是 O(n)。
把圆形项链看成两圈接成的一条线就行——位置 i 的珠子是 S[i % n]，不必真的把字符串接起来。
陷阱一：看成两圈却不把窗口限制在 n 颗以内，同一颗珠子会被数两次——第二个例子 "ab" 中 "aba" 看起来有两个 a，但 a 珠子只有一颗，所以是 -1。
陷阱二：只看成一条线会漏掉像第一个例子那样把最后一颗（d）和第一颗（c）连起来的窗口（从第 6 颗开始，2 颗）。
陷阱三：长度相同时用 <= 替换，会留下最后找到的窗口——窗口按起点从前到后出现，所以只在 < 时替换（起点在 n 及以后的窗口是第一圈里同一个窗口，要排除）。
陷阱四：只看 T 中字母的种类是错的——"aab" 需要两个 a。
把字母变成 0~25 编号的方法各语言不同：Python ord(ch) - 97，JavaScript、TypeScript s.charCodeAt(i) - 97，Java、C#、C、C++ 中字符可以当整数计算，所以是 ch - 'a'，Craykon 的 s[i] 是单个字符的字符串，所以用 字符.编码(s[i]) - 97。
C 像 scanf("%100001s", s) 这样限定宽度读入，Craykon 用 控制台.读行().去空白() 读入一行。
计数表只有 26 格，与 Craykon 的列表上限无关；字符串最多 10,000,000 个字符，所以 100,000 个字符没问题。
import sys lines = 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 + 1 print(f"{best_start + 1} {best_len}" if best_start >= 0 else -1)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");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");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"); }}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"); }}#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";}#include <stdio.h>#include <string.h> #define MAXL 100000 static 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;}// 두 바퀴 붙인 줄의 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);}