A warehouse checks whether product codes fit a given template.
A template is a row of slots from left to right, and each slot checks one character of a code.
A single character outside brackets in the template is one slot, and that slot accepts exactly that character.
In the template, everything from [ up to the first ] after it is one character-class slot, and the string between the two brackets is called its body.
If the body starts with ^, the class is negated. This leading ^ is removed from the body, and the slot accepts only characters that are not described by the rest of the body. A ^ anywhere else is an ordinary character.
The body is read from the left. If the current character is immediately followed by - and there is one more character after that, the three characters a-b mean every character whose ASCII code is at least a and at most b, and reading skips three characters.
Otherwise the current character means just itself, and reading skips one character. So a - at the very start or very end of the body is the - character itself.
The first line gives the template, the second line gives the number of codes n, and the next n lines give one code each.
For each code, the i-th character of the code is checked by the i-th slot of the template (positions count from 1).
Print on one line the first position i where one of these happens: the code has no i-th character, the template has no i-th slot, or the i-th slot does not accept the i-th character.
If the code has as many characters as the template has slots and every slot accepts its character, print 0.
Input
The template has 1 to 200 characters and 1 to 100 slots. Every character of the template and the codes is a non-space ASCII character (codes 33 to 126). Every [ in the template has a ] after it that closes its slot, no body contains [, and there is no ] outside brackets. A body has at least one character even without a leading ^, and in every range a-b the code of a ≤ the code of b. 1 ≤ n ≤ 1,000. Each code has 1 to 100 characters
Output
n lines
Example 1 · stdin
[A-Z][a-z_-][0-9]
6
Ab3
A-7
a_1
B_
Cd45
Z^0
stdout
0
0
1
3
4
2
Example 2 · stdin
#[^0-9^][A-z]
8
#a_
#^a
#x\
#x[
x
#5Q
#~`
#Q@
stdout
0
2
0
0
1
2
0
3
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
These are the rules of a regex character class [...]. Collect the accepted characters of each slot up front and then just ask whether a character is in it: Python c in s (a set), JS/TS set.has(c), in Java, C# and C a 128-entry bool array indexed by character code, C++ std::bitset<128>, Craykon Contains on a Dict. For a negated slot, the character is wrong when (is in it) == negated. Trap ① a range includes both ends. Python range(ord(a), ord(b)) leaves out b. ② - makes a range only between two characters. A - at the start or end is the character -, and a-c-e is a-c, -, e. ③ ^ negates only at the very start. The ^ in [a^] is just a character. ④ A-z is not only letters. Codes 91 to 96, [\]^_ and the backquote (` `), are inside it too, so replacing the range with isalpha, Character.isLetter or char.IsLetter is wrong. ⑤ A membership test on the string loses the ranges. Python c in "a-z", JS "a-z".includes(c) and Craykon "a-z".Contains(c) only see the three characters a, -, z. ⑥ Different lengths are also wrong. Comparing only up to the shorter one prints 0 for a code that is missing characters, like B_. Positions count from 1. In C, cast a character to (unsigned char) before using it as an array index (char` may be negative).
Pythonmain.py · 46 lines
import sysdef parse(pattern): """틀을 칸 목록으로 바꾼다. 칸 하나는 (뒤집기, 받는 글자 집합)이다.""" slots = [] i = 0 while i < len(pattern): if pattern[i] != "[": slots.append((False, {pattern[i]})) # 대괄호 밖 글자는 그 글자 하나만 i += 1 continue end = pattern.index("]", i) body = pattern[i + 1:end] neg = body.startswith("^") # ^는 맨 앞에 있을 때만 뒤집기 if neg: body = body[1:] chars = set() j = 0 while j < len(body): if j + 2 < len(body) and body[j + 1] == "-": # a-b: 코드가 a 이상 b 이하인 글자 모두(두 끝 포함) chars.update(chr(c) for c in range(ord(body[j]), ord(body[j + 2]) + 1)) j += 3 else: chars.add(body[j]) # 맨 앞·맨 끝의 -는 그냥 글자 j += 1 slots.append((neg, chars)) i = end + 1 return slotsdef first_bad(slots, t): for i in range(max(len(slots), len(t))): if i >= len(slots) or i >= len(t): return i + 1 # 글자가 모자라거나 남는다 neg, chars = slots[i] if (t[i] in chars) == neg: # 뒤집힌 칸은 들어 있으면 안 된다 return i + 1 return 0lines = sys.stdin.read().split("\n")slots = parse(lines[0].strip())n = int(lines[1])print("\n".join(str(first_bad(slots, t.strip())) for t in lines[2:2 + n]))
JavaScriptmain.js · 44 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");// 틀을 칸 목록으로 바꾼다. 칸 하나는 { neg, chars(Set) }다function parse(pattern) { const slots = []; let i = 0; while (i < pattern.length) { if (pattern[i] !== "[") { slots.push({ neg: false, chars: new Set([pattern[i]]) }); // 대괄호 밖 글자는 그 글자 하나만 i++; continue; } const end = pattern.indexOf("]", i); let body = pattern.slice(i + 1, end); const neg = body.startsWith("^"); // ^는 맨 앞에 있을 때만 뒤집기 if (neg) body = body.slice(1); const chars = new Set(); for (let j = 0; j < body.length; ) { if (j + 2 < body.length && body[j + 1] === "-") { // a-b: 코드가 a 이상 b 이하인 글자 모두(두 끝 포함) for (let c = body.charCodeAt(j); c <= body.charCodeAt(j + 2); c++) chars.add(String.fromCharCode(c)); j += 3; } else { chars.add(body[j]); // 맨 앞·맨 끝의 -는 그냥 글자 j++; } } slots.push({ neg, chars }); i = end + 1; } return slots;}function firstBad(slots, t) { for (let i = 0; i < Math.max(slots.length, t.length); i++) { if (i >= slots.length || i >= t.length) return i + 1; // 글자가 모자라거나 남는다 if (slots[i].chars.has(t[i]) === slots[i].neg) return i + 1; // 뒤집힌 칸은 들어 있으면 안 된다 } return 0;}const slots = parse(lines[0].trim());const n = Number(lines[1]);console.log(lines.slice(2, 2 + n).map((t) => firstBad(slots, t.trim())).join("\n"));
TypeScriptmain.ts · 51 lines
import { readFileSync } from "node:fs";interface Slot { neg: boolean; chars: Set<string>;}const lines: string[] = readFileSync(0, "utf8").split("\n");// 틀을 칸 목록으로 바꾼다function parse(pattern: string): Slot[] { const slots: Slot[] = []; let i = 0; while (i < pattern.length) { if (pattern[i] !== "[") { slots.push({ neg: false, chars: new Set([pattern[i]]) }); // 대괄호 밖 글자는 그 글자 하나만 i++; continue; } const end = pattern.indexOf("]", i); let body = pattern.slice(i + 1, end); const neg = body.startsWith("^"); // ^는 맨 앞에 있을 때만 뒤집기 if (neg) body = body.slice(1); const chars = new Set<string>(); for (let j = 0; j < body.length; ) { if (j + 2 < body.length && body[j + 1] === "-") { // a-b: 코드가 a 이상 b 이하인 글자 모두(두 끝 포함) for (let c = body.charCodeAt(j); c <= body.charCodeAt(j + 2); c++) chars.add(String.fromCharCode(c)); j += 3; } else { chars.add(body[j]); // 맨 앞·맨 끝의 -는 그냥 글자 j++; } } slots.push({ neg, chars }); i = end + 1; } return slots;}function firstBad(slots: Slot[], t: string): number { for (let i = 0; i < Math.max(slots.length, t.length); i++) { if (i >= slots.length || i >= t.length) return i + 1; // 글자가 모자라거나 남는다 if (slots[i].chars.has(t[i]) === slots[i].neg) return i + 1; // 뒤집힌 칸은 들어 있으면 안 된다 } return 0;}const slots = parse(lines[0].trim());const n = Number(lines[1]);console.log(lines.slice(2, 2 + n).map((t) => firstBad(slots, t.trim())).join("\n"));
JavaMain.java · 57 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main { // 칸 하나: 글자 코드 0~127마다 받는지(ok)를 적은 표 static List<boolean[]> parse(String pattern) { List<boolean[]> slots = new ArrayList<>(); int i = 0; while (i < pattern.length()) { boolean[] ok = new boolean[128]; if (pattern.charAt(i) != '[') { ok[pattern.charAt(i)] = true; // 대괄호 밖 글자는 그 글자 하나만 slots.add(ok); i++; continue; } int end = pattern.indexOf(']', i); String body = pattern.substring(i + 1, end); boolean neg = body.startsWith("^"); // ^는 맨 앞에 있을 때만 뒤집기 if (neg) body = body.substring(1); for (int j = 0; j < body.length(); ) { if (j + 2 < body.length() && body.charAt(j + 1) == '-') { for (char c = body.charAt(j); c <= body.charAt(j + 2); c++) ok[c] = true; // 두 끝 포함 j += 3; } else { ok[body.charAt(j)] = true; // 맨 앞·맨 끝의 -는 그냥 글자 j++; } } if (neg) for (int c = 0; c < 128; c++) ok[c] = !ok[c]; slots.add(ok); i = end + 1; } return slots; } static int firstBad(List<boolean[]> slots, String t) { int len = Math.max(slots.size(), t.length()); for (int i = 0; i < len; i++) { if (i >= slots.size() || i >= t.length()) return i + 1; // 글자가 모자라거나 남는다 if (!slots.get(i)[t.charAt(i)]) return i + 1; } return 0; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); List<boolean[]> slots = parse(in.readLine().trim()); int n = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int k = 0; k < n; k++) out.append(firstBad(slots, in.readLine().trim())).append('\n'); System.out.print(out); }}
C#Main.cs · 65 lines
using System;using System.Collections.Generic;using System.Text;class Program{ // 칸 하나: 글자 코드 0~127마다 받는지(ok)를 적은 표 static List<bool[]> Parse(string pattern) { var slots = new List<bool[]>(); int i = 0; while (i < pattern.Length) { var ok = new bool[128]; if (pattern[i] != '[') { ok[pattern[i]] = true; // 대괄호 밖 글자는 그 글자 하나만 slots.Add(ok); i++; continue; } int end = pattern.IndexOf(']', i); string body = pattern.Substring(i + 1, end - i - 1); bool neg = body.StartsWith("^"); // ^는 맨 앞에 있을 때만 뒤집기 if (neg) body = body.Substring(1); for (int j = 0; j < body.Length;) { if (j + 2 < body.Length && body[j + 1] == '-') { for (char c = body[j]; c <= body[j + 2]; c++) ok[c] = true; // 두 끝 포함 j += 3; } else { ok[body[j]] = true; // 맨 앞·맨 끝의 -는 그냥 글자 j++; } } if (neg) for (int c = 0; c < 128; c++) ok[c] = !ok[c]; slots.Add(ok); i = end + 1; } return slots; } static int FirstBad(List<bool[]> slots, string t) { int len = Math.Max(slots.Count, t.Length); for (int i = 0; i < len; i++) { if (i >= slots.Count || i >= t.Length) return i + 1; // 글자가 모자라거나 남는다 if (!slots[i][t[i]]) return i + 1; } return 0; } static void Main() { var slots = Parse(Console.ReadLine().Trim()); int n = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int k = 0; k < n; k++) sb.Append(FirstBad(slots, Console.ReadLine().Trim())).Append('\n'); Console.Write(sb); }}
C++main.cpp · 62 lines
#include <array>#include <bitset>#include <iostream>#include <string>#include <vector>using Slot = std::bitset<128>; // 글자 코드 0~127마다 받는지std::vector<Slot> parse(const std::string &p) { std::vector<Slot> slots; std::size_t i = 0; while (i < p.size()) { Slot s; if (p[i] != '[') { s.set(p[i]); // 대괄호 밖 글자는 그 글자 하나만 slots.push_back(s); i++; continue; } std::size_t end = p.find(']', i); std::string body = p.substr(i + 1, end - i - 1); bool neg = !body.empty() && body[0] == '^'; // ^는 맨 앞에 있을 때만 뒤집기 if (neg) body.erase(0, 1); for (std::size_t j = 0; j < body.size();) { if (j + 2 < body.size() && body[j + 1] == '-') { for (int c = body[j]; c <= body[j + 2]; c++) s.set(c); // 두 끝 포함 j += 3; } else { s.set(body[j]); // 맨 앞·맨 끝의 -는 그냥 글자 j++; } } if (neg) s.flip(); slots.push_back(s); i = end + 1; } return slots;}int firstBad(const std::vector<Slot> &slots, const std::string &t) { std::size_t m = std::max(slots.size(), t.size()); for (std::size_t i = 0; i < m; i++) { if (i >= slots.size() || i >= t.size()) return static_cast<int>(i) + 1; // 모자라거나 남는다 if (!slots[i].test(t[i])) return static_cast<int>(i) + 1; } return 0;}int main() { std::ios::sync_with_stdio(false); std::string p, t; int n; std::cin >> p >> n; // 틀과 질문에는 빈칸이 없다 auto slots = parse(p); std::string out; for (int k = 0; k < n; k++) { std::cin >> t; out += std::to_string(firstBad(slots, t)) + '\n'; } std::cout << out; return 0;}
Cmain.c · 54 lines
#include <stdio.h>#include <string.h>static char ok[100][128]; /* 칸마다 글자 코드 0~127을 받는지 */static int nslots = 0;static void parse(const char *p) { int len = (int)strlen(p), i = 0; while (i < len) { char *s = ok[nslots++]; if (p[i] != '[') { s[(unsigned char)p[i]] = 1; /* 대괄호 밖 글자는 그 글자 하나만 */ i++; continue; } int b = i + 1, end = (int)(strchr(p + i, ']') - p); int neg = p[b] == '^'; /* ^는 맨 앞에 있을 때만 뒤집기 */ if (neg) b++; for (int j = b; j < end;) { if (j + 2 < end && p[j + 1] == '-') { for (int c = (unsigned char)p[j]; c <= (unsigned char)p[j + 2]; c++) s[c] = 1; /* 두 끝 포함 */ j += 3; } else { s[(unsigned char)p[j]] = 1; /* 맨 앞·맨 끝의 -는 그냥 글자 */ j++; } } if (neg) for (int c = 0; c < 128; c++) s[c] = !s[c]; i = end + 1; }}static int first_bad(const char *t) { int len = (int)strlen(t), m = len > nslots ? len : nslots; for (int i = 0; i < m; i++) { if (i >= nslots || i >= len) return i + 1; /* 글자가 모자라거나 남는다 */ if (!ok[i][(unsigned char)t[i]]) return i + 1; } return 0;}int main(void) { char p[256], t[128]; int n; scanf("%255s", p); /* 틀과 질문에는 빈칸이 없다 */ parse(p); scanf("%d", &n); for (int k = 0; k < n; k++) { scanf("%127s", t); printf("%d\n", first_bad(t)); } return 0;}
Craykonmain.cray · 70 lines
틀 = Console.ReadLine().Trim();n = Console.ReadLine().ToNumber();// 칸마다 [뒤집기, 받는 글자 사전]을 만든다칸들 = [];i = 0;while (i < 틀.Length){ 글자들 = Dict(); if (틀[i] != "[") { 글자들[틀[i]] = true; // 대괄호 밖 글자는 그 글자 하나만 칸들.Add([false, 글자들]); i = i + 1; } else { 끝 = i + 1; while (틀[끝] != "]") { 끝 = 끝 + 1; } 본문 = 틀.Substring(i + 1, 끝 - i - 1); 뒤집기 = 본문.StartsWith("^"); // ^는 맨 앞에 있을 때만 뒤집기 if (뒤집기) { 본문 = 본문.Substring(1); } j = 0; while (j < 본문.Length) { if (j + 2 < 본문.Length && 본문[j + 1] == "-") { // a-b: 코드가 a 이상 b 이하인 글자 모두(두 끝 포함) for (c = Str.Code(본문[j]); c <= Str.Code(본문[j + 2]); c++) { 글자들[Str.FromCode(c)] = true; } j = j + 3; } else { 글자들[본문[j]] = true; // 맨 앞·맨 끝의 -는 그냥 글자 j = j + 1; } } 칸들.Add([뒤집기, 글자들]); i = 끝 + 1; }}for (k = 0; k < n; k++){ t = Console.ReadLine().Trim(); 답 = 0; for (p = 0; p < Mathf.Max(칸들.Count, t.Length); p++) { if (p >= 칸들.Count || p >= t.Length) { 답 = p + 1; // 글자가 모자라거나 남는다 break; } if (칸들[p][1].Contains(t[p]) == 칸들[p][0]) { 답 = p + 1; // 뒤집힌 칸은 들어 있으면 안 된다 break; } } Console.WriteLine(답);}