https://codeforces.com/contest/1207/problem/GI'm not good at string problems, but I have solved it luckily. First we construct the Aho-Corasick of the query strings. If N strings is produced by type 2 except the first string, we can direct…