[Codeforces] F. Bracket Substring

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. Bracket Substring
Source            : Codeforces
Category          : Dynamic Programing + String
Algorithm         : Dynamic Programing, KMP
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define vi          vector <int>  
#define eb          emplace_back  
#define ll          long long int  
  
static const int maxn = 200 + 5;  
static const ll  mod = 1e9 + 7;  
  
vi LPS(string pat)  
{  
      int len = pat.size();  
      int i = 1;  
      int j = 0;  
      vi lps;  
      lps.eb(0);  
      while (i < len)  
      {  
            if (pat[i] == pat[j])  
            {  
                  i++;  
                  j++;  
                  lps.eb(j);  
            }  
            else  
            {  
                  if (j) j = lps[j-1];  
                  else lps.eb(0), i++;  
            }  
      }  
      return lps;  
}  
  
vi lps;  
string pat;  
  
int kmp(int id, char brac)  
{  
      while (id > 0 && brac != pat[id]) id = lps[id-1];  
      if (brac == pat[id]) ++id;  
      return id;  
}  
  
ll dp[maxn][maxn][maxn];  
bool memoize[maxn][maxn][maxn];  
int n;  
  
ll solve(int pos, int open, int found)  
{  
      if (pos >= 2*n) return (open == 0 && found >= pat.size());  
      ll &ret = dp[pos][open][found];  
      bool &mem = memoize[pos][open][found];  
      if (mem) return ret;  
      mem = 1;  
      ll choice1 = 0;  
      ll choice2 = 0;  
      {  
            int fnd = found;  
            if (fnd < pat.size()) fnd = kmp(fnd, '(');  
            choice1 = (choice1 + solve(pos+1, open+1, fnd)) % mod;  
      }  
      {  
            if (open)  
            {  
                  int fnd = found;  
                  if (fnd < pat.size()) fnd = kmp(found, ')');  
                  choice2 = (choice2 + solve(pos+1, open-1, fnd)) % mod;  
            }  
      }  
      return ret = (choice1 + choice2) % mod;  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> n >> pat;  
      lps = LPS(pat);  
      cout << solve(0, 0, 0);  
}