Label
Time limit2sMemory limit256 MB
Count the cyclic shifts t of the concatenated label that split into dictionary words separated by one or more dots, and list them.
- Level
Hard8 of 10
- Topics
- String matching, Dynamic programming, Hash map
- Solved
- No attempts yet
Problem
Archaeologists excavating a settlement of an ancient civilization found a bottle label that has survived to today. This civilization drank from bottles with labels describing the drink, just as people do now. Its writing had no line-break marker. When a line ended, reading simply continued on the next line.
The label wrapped around the bottle as a full cylinder, so the text is read starting from the seam. Reading begins with the first line at the seam. Once the reader reaches the seam, they move to the second line, then the third, and so on. The seam position is unknown. What the scientists have is a set of rows, each of the same length , made of lowercase letters and the character ., which this civilization used in place of spaces.
The scientists also have a dictionary listing every word the civilization used. Count the non-negative integers such that concatenating all the given rows, then cyclically shifting the result left by characters, gives a sequence of dictionary words separated by one or more . characters. Output all such values of .
Input
The first line contains one integer (), the number of words in the dictionary. The next lines each contain one dictionary word. All words are distinct, consist only of lowercase Latin letters, and have length at most 2000.
The next line contains one integer (), the number of rows on the label. The next lines contain the rows. Every row consists only of lowercase Latin letters and .. All rows have the same length, at most 2000. Each row contains at least one ..
Output
On the first line, print the number of valid values of . On the second line, print all these values in ascending order, separated by spaces.