読者です 読者をやめる 読者になる 読者になる

Manthan, Codefest 16 C: Spy Syndrome 2

解法

文字列の一致判定はローリングハッシュにしてもらって、メモ化再帰で計算量を減らす。

コード

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

typedef long long ll;

struct ToLower {
  char operator()(char c) { return tolower(c); }
};

class RollingHash {
 private:
  vector<long long> mod;
  void init() {
    // mod.push_back(999999937LL);
    mod.push_back(1000000009LL);
  }
  const long long base = 1000000007LL;
  int n;
  vector<vector<long long> > hs, pw;
  RollingHash() {}

 public:
  int cnt = 0;

  RollingHash(const string& s) : n(s.size()) {
    init();
    hs.resize(mod.size()), pw.resize(mod.size());
    for (int i = 0; i < mod.size(); i++) {
      hs[i].assign(n + 1, 0);
      pw[i].assign(n + 1, 0);
      hs[i][0] = 0;
      pw[i][0] = 1;
      for (int j = 0; j < n; j++) {
        // pw[i][j + 1] = pw[i][j] * base % mod[i];
        // hs[i][j + 1] = (hs[i][j] * base + s[j]) % mod[i];
        pw[i][j + 1] = pw[i][j] * base;
        hs[i][j + 1] = (hs[i][j] * base + s[j]);
      }
    }
  }

  inline long long hash(int l, int r, int i) {
    // return ((hs[i][r] - hs[i][l] * pw[i][r - l]) % mod[i] + mod[i]) % mod[i];
    return hs[i][r] - hs[i][l] * pw[i][r - l];
  }

  inline bool match(int l1, int r1, int l2, int r2) {
    bool ret = 1;
    for (int i = 0; i < mod.size(); i++)
      ret &= hash(l1, r1, i) == hash(l2, r2, i);
    return ret;
  }

  inline bool match(int l1, int l2, int k) {
    return match(l1, l1 + k, l2, l2 + k);
  }

  int lcp(int i, int j) {
    int l = 0, r = min(n - i, n - j) + 1;
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if (match(i, i + m, j, j + m))
        l = m;
      else
        r = m;
    }
    return l;
  }
};

vector<int> dp;
vector<bool> vis;
vector<int> mapping;
vector<int> T_size;
vector<string> T;
int N, M;

bool dfs(RollingHash& lolita, int pos) {
  if (pos == N) return true;
  if (pos >= dp.size() || vis[pos]) return false;
  vis[pos] = true;
  for (int m = 0; m < M; ++m) {
    if (lolita.match(pos, mapping[m], T_size[m]) &&
        dfs(lolita, pos + T_size[m])) {
      dp[pos] = m;
      return true;
    }
  }
  return false;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> N >> S >> M;
  T.resize(M);
  T_size.resize(M);
  mapping.resize(M);
  for (size_t i = 0; i < M; i++) {
    cin >> T[i];
    T_size[i] = T[i].size();
    string t = T[i];
    transform(t.begin(), t.end(), t.begin(), ToLower());
    reverse(t.begin(), t.end());
    S += "?";
    mapping[i] = S.size();
    S += t;
  }

  RollingHash lolita(S);
  dp.assign(N, -1);
  vis.assign(N, false);
  dfs(lolita, 0);
  for (int i = 0; i < N;) {
    if (i > 0) cout << " ";
    cout << T[dp[i]];
    i += T_size[dp[i]];
  }
  cout << endl;
}