SPOJ TESSER

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

const int OO = 1e9;
const double EPS = 1e-9;

int arr[100000];

vector<int> computePrefixes(string s) {
    vector<int> ret(s.length());
    for(int i = 1, k = 0; i < s.length(); i++) {
        while(k > 0 && s[k] != s[i]) {
            k = ret[k-1];
        }
        ret[i] = (s[i] == s[k] ? ++k:k);
    }
    return ret;
}

bool kmp(string s, string p) {
    vector<int> pre = computePrefixes(p);
    for(int i = 0, k = 0; i < s.length(); i++) {
        while(k > 0 && s[i] != p[k]) {
            k = pre[k-1];
        }
        if(s[i] == p[k]) {
            k++;
        }
        if(k == p.length()) {
            return true;
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        string p;
        cin >> p;
        string s = "";
        for(int i = 1; i < n; i++) {
            if(arr[i] > arr[i-1]) {
                s += 'G';
            }
            else if(arr[i] == arr[i-1]) {
                s += 'E';
            }
            else {
                s += 'L';
            }
        }
        cout << (kmp(s,p) ? "YES\n":"NO\n");
    }
    return 0;
}