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 .

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

1. A single integer N (2 ≤ N ≤ 105) denoting the number of data points.
2. N integers (ai, where 1 ≤ ai ≤ 109)
3. 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 <bits/stdc++.h>

using namespace std;

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

for(int i = 0; i < (no - 1); ++i)
{
if(v[i+1] > v[i])
text = text + 'G';
else if(v[i] == v[i+1])
text = text + 'E';
else
text = text + 'L';
}
v.clear();
cin >> pattern;
int n = no - 1;
int m = pattern.length();
vector<int> pi = computePrefixFunction(pattern);
int q = -1;
for(int i = 0; i < n; ++i)
{
while(q > -1 && 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 << "YES\n";
else
cout << "NO\n";
pi.clear();
test_case = test_case - 1;
}
return 0;
}

vector<int> computePrefixFunction(string p)
{
int m = p.length();
vector<int> pi;
pi.push_back(-1);
int k = -1;
for(int q = 1; q < m; ++q)
{
while(k > -1 && p[k+1] != p[q])
k = pi[k];
if(p[k+1] == p[q])
k = k + 1;
pi.push_back(k);
}
return pi;
}


• 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 <bits/stdc++.h> is not standard C++.
• using namespace std defeats the benefits of the namespace, and is not recommended.
• Declaring vector<int> 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 & — 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 <iostream>
#include <string>
#include <utility>
#include <vector>

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

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

/**
* Reads a test case, expecting:
* 1) the number of data points (2 <= n <= 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<std::string, std::string> tesserect(std::istream &in) {
size_t n;
uint32_t prev, curr;
std::string s, pattern;

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

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

int main() {
int testCases;
for (std::cin >> testCases; testCases; --testCases) {
std::pair<std::string, std::string> strings = tesserect(std::cin);

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

std::cout << (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.

The above code given in the question has some problems:

1. Use of string, vector, cin, cout are creating objects of corresponding classes, taking too much time. In that case, those can be replaced by array, printf(), scanf() which saves time.
2. While matching when there are less characters to be matched in a text than no of characters in a pattern, clearly there will be no match and handling that case will save some time.
3. pi array is fully calculated before matching text with pattern. So this can be easily done in main function saving time for function call.(This is optional)
4. Obviously there's no need to store input array as the pattern can be calculated right away. The above code needs to get rid of that.

The modified code is given below and it got accepted in spoj.

int main()
{
char text[100005];
char pattern[100005];
int pi[100009];
pi[0] = -1;
int number, test_case;
long long value1, value2;
scanf("%d", &test_case);
while(test_case--)
{
scanf("%d", &number);
scanf("%lld", &value1);
bool pattern_found = false;

for(int i = 0; i < (number - 1); ++i)
{
scanf("%lld", &value2);
if(value2 > value1)
text[i] = 'G';
else if(value2 == value1)
text[i] = 'E';
else
text[i] = 'L';

value1 = value2;
}
text[number] = '\n';
scanf("%s", &pattern);
int n = number - 1;
int m = strlen(pattern);

int k = -1;
for(int q = 1; q < m; ++q)
{
while(k > -1 && pattern[k+1] != pattern[q])
k = pi[k];
if(pattern[k+1] == pattern[q])
k = k + 1;
pi[q] = k;
}

int q = -1;
if(m <= n)
{
for(int i = 0; i < n; ++i)
{
while(q > -1 && pattern[q+1] != text[i])
q = pi[q];
if(pattern[q+1] == text[i])
q = q + 1;
if(q == (m-1))
{
pattern_found = true;
break;
}
if((m - q) > (n - i)) /*skip if text gets shorter than pattern, saves a lot of time*/
break;
}
}
if(pattern_found == true)
printf("YES\n");
else
printf("NO\n");

}
return 0;
}