Sum of Lengths of Lexicographically Smallest Substrings

Problem Statement

Sum of Lengths of Lexicographically Smallest Substrings Problem Description You are given a string S of length N and Q queries. Each query gives you a query string T , and for every query you must do the following: Collect every substring of S that starts with T (that is, every substring of S whose first |T| characters are exactly T ). Among the substrings collected, find the lexicographically smallest one. Record the length of that lexicographically smallest substring. If no substring of S starts with T , nothing is collected for that query and the recorded length is 0 . Print the sum of the recorded lengths over all Q queries. Input Format The first line contains the string S . The second line contains the integer Q , the number of queries. Each of the next Q lines contains one query string T . Output Format Print a single integer: the sum of the recorded lengths over the Q queries. Examples Example 1 banana 3 a b z Output: 2 For T = "a" the substrings of banana that start with a are