Counting substrings
InterviewTime limit1sMemory limit1024 MB
Count the distinct strings that can be built from some subset of the distinct letters of S and that contain P as a contiguous substring.
- Level
Medium6 of 10
- Topics
- Backtracking, Combinatorics, String, Brute force
- Solved
- No attempts yet
Problem
Strings and consisting of lowercase Latin letters are given.
Write a program substrings that determines the number of distinct words made from the letters of that contain as a substring.
Input
The first line of the standard input contains the string , and the second line contains the string .
Output
On a single line of the standard output, the program must print a single integer: the number of distinct words.
Constraints
- number of characters in the strings
- All characters in the string are distinct.
Hint
Explanation of example 1: The substrings are bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.