만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

라벨

시간 제한2초메모리 제한256 MB

요약
n개의 행을 이어 붙인 문자열을 t칸 순환 이동했을 때, 점(.)으로 구분된 사전 단어들의 나열이 되는 t를 모두 구합니다.
난이도

어려움10점 중 8점

유형
문자열 매칭, 동적 계획법, 해시맵
정답자
아직 제출이 없습니다

문제

고대 문명의 정착지를 발굴하던 고고학자들이 지금까지 남아 있는 병 라벨 하나를 찾았다. 이 문명 사람들도 지금처럼 음료 정보가 적힌 라벨을 붙인 병에서 음료를 마셨다. 다만 이들의 글에는 줄바꿈 표시가 없었다. 한 줄이 끝나면 다음 줄에서 그대로 이어서 읽었다.

라벨은 병을 한 바퀴 감싸는 원통형이므로, 글은 이음매에서 시작해 읽어야 한다. 이음매 위치의 첫 번째 줄부터 읽기 시작하고, 이음매에 도달하면 두 번째 줄, 세 번째 줄 순서로 넘어간다. 이음매의 위치는 아직 알려지지 않았다. 연구자들에게 있는 것은 길이가 모두 kk로 같은 nn개의 줄뿐이다. 각 줄은 소문자 알파벳과, 공백 대신 이 문명이 쓴 기호 .로 이루어져 있다.

연구자들은 이 문명이 쓴 모든 단어가 실린 사전도 가지고 있다. 주어진 줄들을 모두 이어 붙인 뒤 결과를 왼쪽으로 tt 글자만큼 순환 이동했을 때, 사전의 단어들이 하나 이상의 .로 구분되어 늘어선 형태가 되는 0 이상 kk 미만의 정수 tt의 개수를 구하라. 그런 tt 값을 모두 출력하라.

입력

첫 줄에 사전의 단어 수 mm (1≤m≤20001 \le m \le 2000)이 주어진다. 다음 mm개 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 모두 서로 다르며, 소문자 알파벳으로만 이루어지고, 길이는 2000 이하다.

다음 줄에는 라벨의 줄 수 nn (1≤n≤20001 \le n \le 2000)이 주어진다. 다음 nn개 줄에 라벨의 문자열이 주어진다. 각 문자열은 소문자 알파벳과 .로만 이루어지며, 모든 문자열의 길이는 같고 2000 이하다. 각 문자열에는 .가 적어도 하나 있다.

출력

첫 줄에 조건을 만족하는 tt의 개수를 출력한다. 둘째 줄에는 그 tt 값들을 오름차순으로 공백을 두고 출력한다.

예제1

  1. 예제 1

    입력
    2
    uu
    u
    5
    .uu..uu
    .uu...u
    ...uu.u
    .u.u.uu
    uuu.uu.
    
    예상 출력
    2
    1 2