1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <bits/stdc++.h>
using std::vector;

void init_io() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

size_t height, width;
std::string text_a, text_b;
std::string text_a_rev, text_b_rev;
unsigned num_queries;

void read_input() {
  std::cin >> height >> width >> num_queries >> text_a >> text_b;
  assert(text_a.size() == height);
  assert(text_b.size() == width);

  text_a_rev = text_a;
  std::reverse(text_a_rev.begin(), text_a_rev.end());
  text_b_rev = text_b;
  std::reverse(text_b_rev.begin(), text_b_rev.end());
}

struct VertexEntry {
  // First i such that value(a_from, a_to, i, j) > value(a_from, a_to, i, j-1).
  size_t first_horizontal = 0;
  // First i such that value(a_from, a_to, i, j) == value(a_from, a_to-1, i, j).
  size_t first_vertical = 0;
};

vector<VertexEntry> init_vertex_row() {
  vector<VertexEntry> vertex_row(width+1);

  for (size_t col=0; col<=width; ++col) {
    VertexEntry &ve = vertex_row[col];
    ve.first_horizontal = col;
    ve.first_vertical = 0;
  }

  return vertex_row;
}

void update_vertex_row(vector<VertexEntry> &vertex_row, char Achar, std::string_view B) {
  for (size_t col=1; col<=width; ++col) {
    const VertexEntry &ve_left = vertex_row[col-1];
    VertexEntry &ve = vertex_row[col];
    if (ve_left.first_vertical < ve.first_horizontal && B[col-1] != Achar) {
      ve.first_vertical = ve_left.first_vertical;
    } else {
      ve.first_vertical = ve.first_horizontal;
      ve.first_horizontal = ve_left.first_vertical;
    }
  }
}

class HalfSolver {
public:
  HalfSolver(const std::string_view A, const std::string_view B);
  // LCS from (0, col_from..col_to) to (row, col_to)
  void fill_lcs_row(vector<unsigned> &lcs_row, size_t row, size_t col_from, size_t col_to) const;
private:
  vector<vector<uint16_t>> first_horizontal_occurence;
};

HalfSolver::HalfSolver(const std::string_view A, const std::string_view B) {
  first_horizontal_occurence.reserve(A.size());
  vector<VertexEntry> vertex_row = init_vertex_row();
  for (const char Achar : A) {
    update_vertex_row(vertex_row, Achar, B);
    vector<uint16_t> fh_occ(width+1, width+1);
    for (size_t col=0; col <= width; ++col) {
      unsigned fh = vertex_row[col].first_horizontal;
      fh_occ[fh] = col;
    }
    first_horizontal_occurence.push_back(std::move(fh_occ));
  }
}

void HalfSolver::fill_lcs_row(
    vector<unsigned> &lcs_row, size_t row, size_t col_from, size_t col_to) const
{
  const vector<uint16_t> &fh_occ = first_horizontal_occurence[row-1];
  unsigned lcs = 0;
  size_t col = col_to;
  for(;;) {
    lcs_row[col] = lcs;
    if (col==col_from) break;
    lcs += (fh_occ[col] > col_to);
    --col;
  }
}

class LCSSolver {
public:
  LCSSolver(size_t a_top, size_t a_bottom);
  unsigned lcs(size_t a_from, size_t a_to, size_t b_from, size_t b_to);
private:
  unsigned lcs_accross(size_t a_from, size_t a_to, size_t b_from, size_t b_to);
  size_t a_middle;
  LCSSolver *up_solver = nullptr;
  LCSSolver *down_solver = nullptr;
  HalfSolver *up_half_solver = nullptr;
  HalfSolver *down_half_solver = nullptr;
};

LCSSolver::LCSSolver(size_t a_top, size_t a_bottom) {
  a_middle = (a_top + a_bottom) / 2;
  if (a_middle - a_top >= 2) {
    up_solver = new LCSSolver(a_top, a_middle - 1);
  }

  if (a_top < a_middle) {
    up_half_solver =
      new HalfSolver(
          std::string_view(text_a_rev).substr(height - a_middle, a_middle - a_top),
          text_b_rev);
  }

  if (a_bottom - a_middle >= 2) {
    down_solver = new LCSSolver(a_middle + 1, a_bottom);
  }

  if (a_middle < a_bottom) {
    down_half_solver =
      new HalfSolver(
          std::string_view(text_a).substr(a_middle, a_bottom - a_middle),
          text_b);
  }
}

unsigned LCSSolver::lcs(size_t a_from, size_t a_to, size_t b_from, size_t b_to) {
  if (a_to < a_middle) {
    return up_solver->lcs(a_from, a_to, b_from, b_to);
  } else if (a_from > a_middle) {
    return down_solver->lcs(a_from, a_to, b_from, b_to);
  } else {
    return lcs_accross(a_from, a_to, b_from, b_to);
  }
}

// 0..width
vector<unsigned> lcs_accross_up_buffer, lcs_accross_down_buffer;

unsigned LCSSolver::lcs_accross(size_t a_from, size_t a_to, size_t b_from, size_t b_to) {
  if (a_from < a_middle) {
    up_half_solver->fill_lcs_row(
        lcs_accross_up_buffer,
        a_middle - a_from,
        width - b_to,
        width - b_from);
  } else {
    std::fill(
        lcs_accross_up_buffer.begin() + (width-b_to),
        lcs_accross_up_buffer.begin() + (width-b_from) + 1u,
        0u);
  }

  if (a_to > a_middle) {
    down_half_solver->fill_lcs_row(
        lcs_accross_down_buffer,
        a_to - a_middle,
        b_from,
        b_to);
  } else {
    std::fill(
        lcs_accross_down_buffer.begin() + b_from,
        lcs_accross_down_buffer.begin() + b_to + 1u,
        0u);
  }

  unsigned best = 0;
  for (size_t j = b_from; j <= b_to; ++j) {
    const unsigned val = lcs_accross_up_buffer[width - j] + lcs_accross_down_buffer[j];
    best = std::max(best, val);
  }

  return best;
}

void process_queries(LCSSolver *solver) {
  for (unsigned query=0; query < num_queries; ++query) {
    size_t a_from, a_to, b_from, b_to;
    std::cin >> a_from >> a_to >> b_from >> b_to;
    --a_from;
    --b_from;
    const auto lcs = solver->lcs(a_from, a_to, b_from, b_to);
    std::cout << lcs << "\n";
  }
}

int main() {
  init_io();
  read_input();
  lcs_accross_up_buffer.resize(width+1);
  lcs_accross_down_buffer.resize(width+1);

  LCSSolver *solver = new LCSSolver(0, height);
  process_queries(solver);
}