BFS and think the problem reversely

AtCoder ABC 329 E — Stamp

Last Saturday, there is a very nice problem from the AtCoder beginner contest.

The problem can be solved by using BFS if we think the problem reversely. This is not a very standard BFS and it is quit interesting.

Question

See here.

Basic idea

We think the problem reversely. Using t of “ABC” as example, to begin with if we find any ABC, then we can change it to “###” where the “#” means we can put anything as it will be covered by “ABC” later.

By doing this, we can first find all the ABC location and put it into a Queue, after that, we pop one, change it to all “###”, then we can find more qualified ones. For example:

1. ABCBABC
after replace the ABC to ###, we will have:
###B###
2. when pop the first "###", wen can check all possible overlap with this "###" one to find 
next steps.
3. since #B# is valid choice as '#' can be put with anything, we can get
####### 

After doing above, the last step will be check whether all the s’ characters can be replaced as ‘#’.

Solution in C++

#include<iostream>                                                                      
#include<queue>                                                                         
#include<vector>                                                                        
using namespace std;                                                                    
                                                                                        
void update(int i, int n, int m, string &s, string &t, queue<int>&Q, vector<int>& seen){
    if (i < 0 || i + m > n || seen[i])return;                                           
    for (int j = 0; j < m ; ++j){                                                       
        if (s[i + j]  == '#' || s[i + j] == t[j])continue;                              
        else return;                                                                    
    }                                                                                   
    seen[i] = true;                                                                     
    Q.emplace(i);                                                                       
    return;                                                                             
}                                                                                       
int main(){                                                                             
    int n, m;                                                                           
    string s, t;                                                                        
    cin>>n >> m >> s >> t;                                                              
    vector<int> seen(n, 0);                                                             
    queue<int> Q;                                                                       
    for (int i =  0; i < n; ++i){                                                       
        update(i, n, m, s, t, Q, seen);                                                 
    }                                                                                   
    while(!Q.empty()){                                                                  
        auto i = Q.front();Q.pop();                                                     
        for (int j = 0; j < m ; ++j){s[i + j ] = '#';                                   
        }                                                                               
        for (int j = -m + 1; j < m; ++j)                                                
        {                                                                               
            update(i + j, n, m, s, t, Q, seen);                                         
        }                                                                               
    }                                                                                   
    if (s == string(n, '#'))cout << "Yes"<<endl;                                        
    else cout << "No" << endl;                                                          
    return 0;                                                                           
} 

Thanks for reading.