Given three integers p, q, r.↵
Then provide p strings, q strings, and r strings.↵
Find the number of string pairs (AB) that satisfy:↵
↵
A is a prefix of some string in the p strings;↵
↵
B is a suffix of some string in the q strings;↵
↵
The concatenated string AB of A and B is a substring of some string in the r strings.↵
p, q, r are all less than or equal to 300,000, and the total length of the p strings is less than or equal to 300,000, the total length of the q strings is less than or equal to 300,000, and the total length of the r strings is less than or equal to 300,000.↵
Please provide an implementation that runs within 3 seconds and uses no more than 1GB of memory to solve this problem.
Then provide p strings, q strings, and r strings.↵
Find the number of string pairs (AB) that satisfy:↵
↵
A is a prefix of some string in the p strings;↵
↵
B is a suffix of some string in the q strings;↵
↵
The concatenated string AB of A and B is a substring of some string in the r strings.↵
p, q, r are all less than or equal to 300,000, and the total length of the p strings is less than or equal to 300,000, the total length of the q strings is less than or equal to 300,000, and the total length of the r strings is less than or equal to 300,000.↵
Please provide an implementation that runs within 3 seconds and uses no more than 1GB of memory to solve this problem.
