시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 6 6 50.000%

문제

민균이와 준민이는 상범이를 사이에 둔 치밀한 삼각관계이다. 민균이는 감성적인 남자라 상범이에게 자주 영어로 편지를 쓰곤 한다. 이 사실을 안 준민이는 몹시 화가 나, 편지를 가로채 내용을 확인하려는 계획을 짰다. 다행히 계획대로 편지를 가로챘지만, 편지의 내용은 암호화가 되어있어 해독을 해야했다.

창영이는 준민이에게 그 암호화된 편지의 문장(여러개의 단어로 구성) 중 일부만 진짜 편지의 문장임을 알려주었다. 즉, 암호화된 편지에는 진짜 편지의 문장이 있을수도 있고 실제 없지만 꾸며낸 문장이 있을 수도 있다는 것이다. 준민이는 이제 그 암호화된 편지 중에 진짜 편지 문장의 위치를 찾으려고 한다.

편지의 암호화 규칙은 다음과 같다.

진짜 편지에 있는 단어는 항상 어떤 단어로 대체된다.(같은 단어로도 대체 가능하다.) 예를 들어, 진짜 편지 문장이 "doo doom chit doo doom chat"이면, 단어 "doo", "doom", "chit", "chat"이 어떤 단어로 대체되어야 한다는 것이다. 만약 "doo" -> a, "doom" -> b, "chit" -> c, "chat" -> d로 대체되었다면, 진짜 편지 문장은 암호화된 편지에서 "a b c a b d"로 나타날 것이다. 또한, 서로 다른 두 단어는 같은 단어로 대체될 수 없다.

단어들은 항상 소문자이며, 띄어쓰기로 구분되어 있다. 문장은 앞에서 말했듯이, 여러 단어의 연속이다.

준민이를 도와 진짜 편지의 한 문장이 입력으로 주어질 때, 암호화된 편지에서 그 문장이 가장 먼저 나타날 수 있는 위치를 출력하는 프로그램을 작성하자.

입력

첫 줄은 암호화된 편지가 주어진다. 편지의 길이는 10^6을 넘지 않으며, 편지의 끝에는 $라고 표시되어 있다. 당연히 $는 편지의 일부로 보지 않는다.

다음 줄에는 진짜 편지의 문장이 주어지는데, 우리는 암호화된 편지에서 이 문장이 제일 먼저 어디서 나타나는 지를 알아내야한다. 이 문장 길이 역시 10^6을 넘지 않으며, 암호화된 편지와 같은 형식을 가진다.

출력

입력으로 주어진 진짜 편지의 문장이, 주어진 암호화된 편지에서 가장 먼저 나타날 수 있는 위치(문장에서 맨 앞 단어의 위치)를 출력한다.

암호화된 편지에서 첫 단어의 위치는1, 다음 단어의 위치는 2, ... 이며 답은 항상 존재한다고 가정해도 좋다.

또한, 답이 여러개일 경우, 가장 작은 위치를 출력한다.

예제 입력

a a a b c d a b c $
x y $

예제 출력

3

힌트

입력이

xyz abc abc xyz $

abc abc $

일 때, 답은 2이다.