Language: C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define EACH(begin, end) for(auto itr = (begin); itr != (end); itr++)

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int INF = 1001001; // 10^6
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;



int N = 0;
int Q = 0;
string str;
char cell[INF];
int ret = 0;
short dp[INF][INF];
vector<char> t;
vector<char> d;

short canStay(int n, int q){
  if(dp[n][q] != -1) {
    return dp[n][q];
  }else if(q == Q) {
    return 1;
  }else{
    int now = n;
    if(t[q+1] == cell[n]){
      //呪文を受ける
      if(d[q+1] == 'L'){
        now--;
      }else if(d[q+1] == 'R'){
        now++;
      }else{
        DEBUG("WRONG");
      }

      if(now == 0 || now == N+1){
        dp[n][q] = 0;
        return 0;
      } else {
        short ans = canStay(now, q+1);
        dp[n][q] = ans;
        return ans;
      }
    }else{
      //呪文を受けない
      short ans = canStay(n, q+1);
      dp[n][q] = ans;
      return ans;
    }
  }
}

void input() {
  IN(N);
  IN(Q);
  IN(str);
  REP(i,N){
    cell[i+1] = str[i];
  }
  t.push_back('b');
  d.push_back('b');
  REP(i,Q){
    char c;
    char dir;
    IN(c);
    IN(dir);
    t.push_back(c);
    d.push_back(dir);
  }
  REP(i, N+3){
    REP(j, Q+3){
      dp[i][j] = -1; //初期化
    }
  }
}

void solve() {
  REP(i,N){
    short ans = canStay(i+1,0);
    if(ans == 1){
      ret++;
    }
  }
  // REP(i, N){
  //   REP(j, Q){
  //     DEBUG(dp[i+1][j]);
  //   }
  //   DEBUG("\n");
  // }
}

int main(void){
  input();
  solve();
  PRINT(ret);
}


Compiler output:
/tmp/cc5iA60v.o: in function `canStay(int, int)':
a.cc:(.text+0x8a): relocation truncated to fit: R_X86_64_PC32 against symbol `t' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0xc4): relocation truncated to fit: R_X86_64_PC32 against symbol `d' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0xf0): relocation truncated to fit: R_X86_64_PC32 against symbol `d' defined in .bss section in /tmp/cc5iA60v.o
/tmp/cc5iA60v.o: in function `input()':
a.cc:(.text+0x2ae): relocation truncated to fit: R_X86_64_PC32 against symbol `t' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0x2c8): relocation truncated to fit: R_X86_64_PC32 against symbol `d' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0x313): relocation truncated to fit: R_X86_64_PC32 against symbol `t' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0x329): relocation truncated to fit: R_X86_64_PC32 against symbol `d' defined in .bss section in /tmp/cc5iA60v.o
/tmp/cc5iA60v.o: in function `__static_initialization_and_destruction_0()':
a.cc:(.text+0x46b): relocation truncated to fit: R_X86_64_PC32 against symbol `t' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0x484): relocation truncated to fit: R_X86_64_PC32 against symbol `t' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0x49d): relocation truncated to fit: R_X86_64_PC32 against symbol `d' defined in .bss section in /tmp/cc5iA60v.o
a.cc:(.text+0x4b6): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status