SWERC 2013/14 - H

#include <bits/stdc++.h>

#define MAXN 400000
#define mod 21092013

using namespace std;
typedef long long ll;

string S_, T_;
vector<char>S;
vector<int> us, nL, nR, nok, ok2s;
int n;

ll memo[MAXN];


// Simple recursion for counting
ll dp(int id){
    if(id == n) return 0; //
    if(memo[id] == -1)
        memo[id] =(ok2s[id] + dp(nL[id]) + dp(nR[id]))%mod;
    return memo[id];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;
    for(int cs = 1; cs <= t; cs++){
        cout << "Case " << cs << ": ";
        cin >> S_ >> T_;

        S.clear();

        S.push_back(' '); // root of the tree

        // get rid of U's in S_
        for(int i = 0; i < (int)S_.size(); i++){
            if(S_[i] == 'U'){ if(S.size() > 1) S.pop_back(); }
            else S.push_back(S_[i]);
        }

        int bx = S.size(); // new size of S -> the immutable  instructions

        us.clear(); int la = 0;
        nok.assign(T_.size()+1, 0); // nok will keep track of next character that's not 'U'
        for(int i = T_.size()-1; i >= 0; i--){
            if(T_[i] != 'U') nok[i] = ++la;
            else nok[i] = nok[i+1];
        }

        // Keeping track of 'U's int T
        for(int i = 0; i < (int)T_.size(); i++){
            if(T_[i] == 'U') us.push_back(nok[i]);
            else S.push_back(T_[i]);
        }

        n = S.size();
        int nxtL = n, nxtR = n;


        ok2s.assign(n+1,1); // keeps track of indexes where you're able to stop
        nL.assign(n+1,n); nR.assign(n+1,n); // position of next letter L/ next letter R

        for(int i = n-1; i >= 0; i--){
            nL[i] = nxtL; nR[i] = nxtR;
            if(S[i] == 'L') nxtL = i;
            else nxtR = i;
        }

        // nL and nR are different for indexes from S
        for(int i = 0; i < bx-1; i++){
            ok2s[i] = 0;
            nL[i] = nR[i] = n;
            if(S[i+1] == 'L')
                nL[i] = i+1;
            else
                nR[i] = i+1;
        }

        // Update indexes in S reachable from T
        for(int i = 0; i < (int)us.size(); i++){
            int u_cnt = min(i+2, bx);

            ok2s[bx-u_cnt] = 1;

            nL[bx - u_cnt] = min(nL[bx - u_cnt], nL[S.size() - us[i]]);
            nR[bx - u_cnt] = min(nR[bx - u_cnt], nR[S.size() - us[i]]);
        }

        memset(memo,-1,sizeof memo);


        cout << dp(0) << '\n';
    }
}