Returning Home

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 512M

Problem type

After a long day, Adam is on his way home. However, after suffering a sudden bout of amnesia, he has forgotten the name of the street where he lives!

Fortunately, he has a list of N potential names, from S_1 to S_n, which are composed of lowercase Latin characters, all with equal length. He also has a set of M quirky constraints that the street name should satisfy; each constraint is of the form [L_i, R_i], meaning that the substring from L_i to R_i should be a palindrome. (Recall that a palindrome is a string which reads the same forwards and backwards, like racecar or tacocat).

Can you help Adam figure out the total number of strings on his list that satisfy these constraints?


For all subtasks:

1 \le N \le 5000

1 \le M \le 500\,000

1 \le |S_i| \le 30, |S_i| = |S_{i+1}| for all integer i from 1 to N-1.

1 \le L_i \le R_i \le |S_i|

Subtask 1 [20%]

1 \le M \le 30

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain the values for N, M, and |S_i|, denoting the number of strings, number of queries, and the length of each string.

The next N lines will contain S_i, the i^\text{th} string Adam is considering.

The next M lines after that will contain two numbers L_i and R_i, denoting the substring from L_i to R_i which must be a palindrome.

Output Specification

Print out, on a single line, the number of strings that Adam is considering which satisfies the constraints.

Sample Input 1

3 2 8
3 3
2 8

Sample Output 1


Explanation for Sample Output 1

Though all three candidate strings satisfy the first constraint, only the second and third strings satisfy the 2^\text{nd} to 8^\text{th} letter being also a palindrome.

Sample Input 2

2 2 3
1 3
2 3

Sample Output 2


Explanation for Sample Output 2

Only the first string satisfies both the string itself being a palindrome and the substring [2, 3] also being a palindrome.


There are no comments at the moment.