26041번 - 비슷한 전화번호 표시

n개의 전화번호가 공백으로 구분된 문자열 A가 주어진다. 문자열 A에는 중복된 전화번호가 존재할 수 있다. 추가로, 하나의 전화번호 B가 주어진다. 전화번호는 문자 ‘1’ ~ 문자 ‘9’로 이루어진 문자열이다. 문자열 A에 포함된 전화번호 중에서 전화번호 B와 다르면서 B를 접두사로 갖는 전화번호의 개수를 출력하자. 전화번호 T의 접두사는 T의 첫 번째 문자부터 한 개 이상의 연속된 문자로 구성된 부분 문자열을 의미한다. 예를 들어, 전화번호 T=’1234’의 접두사는 전화번호 ‘1’, ‘12’, ‘123’, '1234'이다.

첫 번째 줄에 문자열 A가 주어진다.

두 번째 줄에 전화번호 B가 주어진다.

문자열 A에 포함된 전화번호 중에서 전화번호 B와 다르면서 B를 접두사로 갖는 전화번호의 개수를 출력한다.

• 1 ≤ n ≤ 100,000
• 2 ≤ 문자열 A 길이 ≤ 1,000,000
• 2 ≤ 전화번호 길이 ≤ 10
• 전화번호는 문자 ‘1’ ~ 문자 ‘9’로 이루어진 문자열이다.