Words Containing a Fixed Substring
Autumn Tournament (2014)
Submission name: substrings.cpp
Problem summary
Using each letter of S at most once, form distinct nonempty words of any length that contain P as one contiguous substring. Count these words. All letters of S are distinct.
Input
S and P on separate lines.
Output
The number of valid distinct words.
Constraints
1 ≤ |S|,|P| ≤ 16; lowercase Latin letters; all letters of S are distinct.
Worked example
Original statement sample.
Input
dcba bc
Output
11
Solution analysis
- If P repeats a letter or contains a letter absent from S, the answer is zero. Otherwise its letters are reserved. Let m=|S|−|P| be the number of remaining letters.
- Treat P as one indivisible block. Choose r of the m other letters, then arrange these r distinct letters and the block in (r+1)! ways. Summing C(m,r)·(r+1)! over r=0…m counts every possible word length.
- For dcba and bc, m=2. Using no extra letters gives bc (1 way); using one of a,d gives 2·2!=4 ways; using both gives 3!=6 ways. The answer is 1+4+6=11. The term for r+1 can be obtained from the term for r by multiplying by (m−r)(r+2)/(r+1), keeping every calculation integral.
Why it works
Every valid word contains P exactly once because no letter may repeat. Contracting that occurrence gives a unique arrangement of the block and a chosen subset of remaining letters. Expanding the block reverses this transformation, so the counted arrangements are in bijection with valid words.
Watch out. These are words formed from arbitrary subsets, not only permutations of all of S and not only substrings of the original order. Repeated letters in P make the answer zero. Use long long for factorial-sized counts.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
string letters;
string pattern;
cin>>letters>>pattern;
array<bool,26>available{};
for(char letter:letters){
available[letter-'a']=true;
}
for(char letter:pattern){
if(!available[letter-'a']){
cout<<0<<'\n';
return 0;
}
available[letter-'a']=false;
}
int remaining=static_cast<int>(letters.size()-pattern.size());
long long term=1;
long long answer=1;
for(int chosen=0;chosen<remaining;chosen++){
// Update C(m,r) * (r+1)! without computing factorial tables.
term=term*(remaining-chosen)*(chosen+2)/(chosen+1);
answer+=term;
}
cout<<answer<<'\n';
}