Find String in a Grid (Problem D, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 5 sec
Memory limit: 256MB
Author: Wiwit Rifai'

# Problem Statement

You have a grid $G$ containing $R$ rows (numbered from 1 to $R$, top to bottom) and $C$ columns (numbered from 1 to $C$, left to right) of uppercase characters. The character in the $r^{\text{th}}$ row and the $c^{\text{th}}$ column is denoted by $G_{r,c}$. You also have $Q$ strings containing uppercase characters. For each of the string, you want to find the number of occurrences of the string in the grid.

An occurrence of string $S$ in the grid is counted if $S$ can be constructed by starting at one of the cells in the grid, going right 0 or more times, and then going down 0 or more times. Two occurrences are different if the set of cells used to construct the string is different. Formally, for each string $S$, you would like to count the number of tuples $\langle r, c, \Delta r, \Delta c \rangle$ such that:

- $1 \le r \le R$ and $r \le r + \Delta r \le R$
- $1 \le c \le C$ and $c \le c + \Delta c \le C$
- $S = G_{r,c} G_{r,c+1} \dots G_{r,c+\Delta c} G_{r+1,c+\Delta c} \dots G_{r+\Delta r,c+\Delta c}$

# Input

Input begins with a line containing three integers: $R\ C\ Q$ ($1 \le R, C \le 500$; $1 \le Q \le 200,\!000$) representing the size of the grid and the number of strings, respectively. The next $R$ lines each contains $C$ uppercase characters representing the grid. The $c^{\text{th}}$ character on the $r^{\text{th}}$ line is $G_{r,c}$. The next $Q$ lines each contains a string $S$ containing uppercase characters. The length of this string is a positive integer not more than $200,\!000$. The sum of the length of all $Q$ strings combined is not more than $200,\!000$.

# Output

For each query in the same order as input, output in a line an integer representing the number of occurrences of the string in the grid.

# Sample Input #1
```
3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A
```
# Sample Output #1
```
2
3
1
0
2
```

*Explanation for the sample input/output #1*

- There are 2 occurrences of “ABC”, represented by the tuples ⟨1,1,1,1⟩ and ⟨1,1,0,2⟩.
- There are 3 occurrences of “BC”, represented by the tuples ⟨1,2,0,1⟩, ⟨1,2,1,0⟩, and ⟨2,1,0,1⟩.
- There is 1 occurrence of “BD”, represented by the tuple ⟨2,1,1,0⟩.
- There is no occurrence of “AC”.
- There are 2 occurrences of “A”, represented by the tuples ⟨1,1,0,0⟩ and ⟨3,2,0,0⟩.

# Sample Input #2
```
2 3 3
AAA
AAA
A
AAA
AAAAA
```
# Sample Output #2
```
6
4
0
```

Sample inputs:
3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A

2 3 3
AAA
AAA
A
AAA
AAAAA

Sample outputs:
2
3
1
0
2

6
4
0

# Solution Analysis
Analysis author: Wiwit Rifai'

To count the number of occurrences of the string $S_i$ in the grid, we can try each character position on $S_i$ as a turning point. So, the total number of tries are $\sum_{i=1}^Q |S_i| \leq 200000$. Let us choose $j^{th}$ character position as the turning point, then the string $S_i$ is consisted of a horizontal string $H$ and a vertical string $V$. The string $H$ is $S_{i1}S_{i2}\ldots S_{ij}$ and the string $V$ is $S_{ij}S_{ij+1}\ldots S_{i|S_i|}$. To make the explanation become easier, we will reverse the string $H$ as $S_{ij}S_{ij-1}\ldots S_{i1}$.

For case $|H| = 1$, we can ignore $H$ and count the number of occurrences of string $V$ vertically with a suffix array. The suffix array will sort every cell $(r, c)$ based on the suffix string $G_{r,c}G_{r+1,c}\ldots G_{R,c}$. So, every vertical occurrences of string $V$ on the grid will be adjacent each other in the suffix array, so we can count the number of occurrences of string $V$ based on the longest common prefix of every adjacent indices on suffix array and use binary search with the help of data structure such as range minimum query to find the range of the occurrences of string $V$. We can insert all query strings to the suffix array before so that we can know the starting position to do the binary search.

The equivalent process is also applicable for case $|V| = 1$, i.e. we can find the number of occurrences of string $H$ horizontally with suffix array by sorting every cell $(r, c)$ based on the suffix string $G_{r,c}G_{r,c-1}\ldots G_{r,1}$.

If $|V| \ne 1$ and $|H| \ne 1$, then we can combine those 2 suffix arrays. Suppose the position of cell $(r, c)$ on the first suffix array (based on vertical suffix) is $X_{r,c}$ and the position of cell $(r, c)$ on the second suffix array (based on horizontal suffix) is $Y_{r,c}$. Since every occurrences of string $V$ are adjacent on first suffix array (e.g. it starts from $L_V$ until $R_V$) and every occurrences of string $H$ are adjacent on second suffix array (e.g. it starts from $L_H$ until $R_H$), then to combine $V$ and $H$ become together, we need to count how many cell $(r, c)$ that satisfying $L_V \le X_{r,c} \le R_V$ and $L_H \le Y_{r,c} \le R_H$.

We can model the rest problem as 2-D Cartesian coordinates. Each cell will be modeled as a point $(X_{r,c}, Y_{r,c})$ and each try on choosing the turning point will become a rectangle from point $(L_V, L_H)$ until point $(R_V, R_H)$. So, the rest problem is to count how many points inside each rectangle. This problem can be solved by data structure such as range tree or we can also use line sweep technique and use range sum query data structure such as BIT or segment tree.

The time-complexity of this solution is:
$$
O((R \times C + \sum_{i=1}^Q |S_i|) \times \log(R \times C + \sum_{i=1}^Q |S_i|)).
$$


Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}