LeetCode Weekly Contest 182 4問目 - Find All Good Strings [1397]

Source

LeetCode Weekly Contest 182
問題文

問題概要

省略

解法

省略

cLay（version 20200325-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

Modint dp[501][2][2][51];

class Solution {
public:
  int findGoodStrings(int n, string s1, string s2, string evil) {
    dummy_main();

    int m = evil.size(), e[51];
    int st, ed, sx, sy, sj;
    Modint res = 0;

    AhoCorasick_Sum<int> aho;
    rep(i,n) (s1[i], s2[i]) -= 'a';
    rep(i,m) e[i] = evil[i] - 'a';
    aho.malloc(m+1, 26);
    aho.init();
    aho.addWord(e, m, 1);
    aho.construct();
    m = aho.node;

    rep(i,n+1) rep(x,2) rep(y,2) rep(j,m) dp[i][x][y][j] = 0;
    dp[0][0][0][0] = 1;

    rep(i,n) rep(x,2) rep(y,2) rep(j,m){
      st = if[x,0,s1[i]];
      ed = if[y,25,s2[i]];
      rep(k,st,ed+1){
        sj = aho.next(j, k);
        if(aho.sum[sj]) continue;
        sx = if[k > s1[i], 1, x];
        sy = if[k < s2[i], 1, y];
        dp[i+1][sx][sy][sj] += dp[i][x][y][j];
      }
    }
    rep(x,2) rep(y,2) rep(j,m) res += dp[n][x][y][j];

    aho.free();
    return res;
  }
};

Current time: 2024年04月20日17時20分45秒
Last modified: 2020年03月30日02時54分44秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)