3347 - Ancestralidade

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

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, p; cin >> n >> p;

  vector<string> s(n);
  string t;

  for (int i = 0; i < p; i++) {
    cin >> s[i];
  }

  cin >> t;

  vector<pair<string, int>> ans;

  for (int i = 0; i < n;) {
    int best = -1, sz = 0;
    for (int j = 0; j < p; ++j) {
      int pos = i;
      while (pos < n and s[j][pos] == t[pos]) {
        ++pos;
      }
      if (pos - i > sz) {
        best = j;
        sz = pos - i;
      }
    }
    if (best == -1) {
      ans.push_back({string(1, t[i]), -1});
      i++;
    } else {
      ans.push_back({t.substr(i, sz), best + 1});
      i += sz;
    }
  }

  for (auto [str, best] : ans) {
    cout << str << ' ' << best << '\n';
  }
}