SPOJ "TESSER" - Getting TLE using KMP algorithm The TESSER - Finding the Tesserect problem is tagged as a problem to be solved by Knuth-Morris-Pratt (KMP) algorithm. I'm using KMP, but am still getting time-limit-exceeded.

Task

Each of T test cases (1 ≤ T ≤ 105) consists of three lines:


A single integer N (2 ≤ N ≤ 105) denoting the number of data points.
N integers (ai, where 1 ≤ ai ≤ 109)
A message pattern (a string consisting only of letters G, L, and E).


In the sequence of ai, each element may be greater than (G), less than (L), or equal to (E) the preceding element.  Find out whether there is some substring of consecutive elements within the sequence that matches the given message pattern, and print "YES" if it is found or "NO" if it is not found.

Example

Input:

1
5
1 2 3 4 1
GGL


Output:

YES


The answer is "YES", because 2 3 4 1 satisfies the pattern GGL, i.e. 3 is greater than 2, 4 is greater than 3, 1 is less than 4.



Here is the code that I submitted:

#include &lt;bits/stdc++.h&gt;

using namespace std;

int main()
{
    string text, pattern;
    vector&lt;int&gt; computePrefixFunction(string p);
    vector&lt;long long int&gt; v;
    int no, test_case;
    long long value;
    cin &gt;&gt; test_case;
    while(test_case)
    {
        cin &gt;&gt; no;
        bool flag = false;
        for(int i = 0; i &lt; no; ++i)
        {
            cin &gt;&gt; value;
            v.push_back(value);
        }

        for(int i = 0; i &lt; (no - 1); ++i)
        {
            if(v[i+1] &gt; v[i])
                text = text + 'G';
            else if(v[i] == v[i+1])
                text = text + 'E';
            else
                text = text + 'L';
        }
        v.clear();
        cin &gt;&gt; pattern;
        int n = no - 1;
        int m = pattern.length();
        vector&lt;int&gt; pi = computePrefixFunction(pattern);
        int q = -1;
        for(int i = 0; i &lt; n; ++i)
        {
            while(q &gt; -1 &amp;&amp; pattern[q+1] != text[i])
                q = pi[q];
            if(pattern[q+1] == text[i])
                q = q + 1;
            if(q == (m-1))
            {
                flag = true;
                break;
            }
        }

        if(flag == true)
            cout &lt;&lt; "YES\n";
        else
            cout &lt;&lt; "NO\n";
        pi.clear();
        test_case = test_case - 1;
    }
    return 0;
}

vector&lt;int&gt; computePrefixFunction(string p)
{
    int m = p.length();
    vector&lt;int&gt; pi;
    pi.push_back(-1);
    int k = -1;
    for(int q = 1; q &lt; m; ++q)
    {
        while(k &gt; -1 &amp;&amp; p[k+1] != p[q])
            k = pi[k];
        if(p[k+1] == p[q])
            k = k + 1;
        pi.push_back(k);
    }
    return pi;
}
Before addressing your performance problem, I'd like to discuss the readability of your code:


It's not immediately obvious that there are T test cases, all independent of each other.  while (test_case) { …; test_case = test_case - 1; } would be clearer if written as

while (test_case--) {
    …
}


All of the variables used in each test case (text, pattern, v, etc.) should be declared inside the loop, to make it clear that no state persists between cases, other than the test_case counter.  That would be less error-prone than calling .clear() to reuse the vectors.

Better yet, define a helper function for handling one test case.  Then it will be obvious that there should be no side-effects.
What is flag?  Flag variables, especially poorly named ones, are a code smell.  At the very least, rename it to pattern_found.

For a program whose main functionality is performing a substring search, it is baffling that nothing like a find(needle, haystack) function appears in your code.  That would be a more appropriate fix for your flag variable.
no is a weird name for an integer variable, yes?
Why bother building v and throwing it away?  You could just construct text directly.


In addition, there are some abuses of C++.


#include &lt;bits/stdc++.h&gt; is not standard C++.
using namespace std defeats the benefits of the namespace, and is not recommended.
Declaring vector&lt;int&gt; computePrefixFunction(string p) inside your main() function is highly unconventional.  Declarations usually go before the function or in a header file.  Better yet, put if you put main() at the end, you won't even need any declaration.
computePrefixFunction(string p) should accept a const std::string &amp; — otherwise you end up copying the string.

I would drop "compute" and "function" from the function name, since those words don't contribute to the meaning.


I recommend the following outline for the code.  Note that you can replace the call to kmpFind() with std::string::find() and still get the same answer (though not necessarily with the right performance characteristics).

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;utility&gt;
#include &lt;vector&gt;

static std::vector&lt;std::string::size_type&gt; kmpPrefixTable(const std::string &amp;w) {
    std::string::size_type candidate = 0;
    std::vector&lt;std::string::size_type&gt; t;
    t.reserve(w.length());
    for (std::string::size_type pos = 2; pos &lt; w.length(); ) {
        …
    }
    return t;
}

/**
 * https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
 */
std::string::size_type kmpFind(const std::string &amp;s, const std::string &amp;w) {
    std::vector&lt;std::string::size_type&gt; t = kmpPrefixTable(w);
    for (std::string::size_type m = 0, i = 0; m + i &lt; s.length(); ) {
        …
    }
    return std::string::npos;
}


/**
 * Reads a test case, expecting:
 * 1) the number of data points (2 &lt;= n &lt;= 1e5),
 * 2) the sequence of data points (space-separated integers, each up to 1e9),
 * 3) the pattern to look for (a string consisting of letters 'G', 'L', and 'E').
 *
 * Returns the sequence (represented as a string, using 'G', 'L', 'E' to
 * represent an increase, decrease, or equality relative to the preceding
 * number), and the pattern to look for.
 */
std::pair&lt;std::string, std::string&gt; tesserect(std::istream &amp;in) {
    size_t n;
    uint32_t prev, curr;
    std::string s, pattern;

    std::cin &gt;&gt; n;
    s.reserve(n);
    for (in &gt;&gt; prev; --n; prev = curr) {
        in &gt;&gt; curr;
        s += (curr &lt; prev) ? 'L' :
             (curr &gt; prev) ? 'G' : 'E';
    }

    in &gt;&gt; pattern;
    return std::make_pair(s, pattern);
}

int main() {
    int testCases;
    for (std::cin &gt;&gt; testCases; testCases; --testCases) {
        std::pair&lt;std::string, std::string&gt; strings = tesserect(std::cin);

        // Equivalent to: pos = strings.first.find(strings.second);
        std::string::size_type pos = kmpFind(strings.first, strings.second);

        std::cout &lt;&lt; (pos != std::string::npos ? "YES\n" : "NO\n");
    }
}


Now, with the Knuth-Morris-Pratt algorithm moved into its own function, you can test and analyze it properly.  You seem to be using a variant that is different from the algorithm given in Wikipedia.  The version in Wikipedia doesn't use nested while loops — you may find it easier to analyze its performance.