結果
問題 | No.1909 Detect from Substrings |
ユーザー |
|
提出日時 | 2022-04-23 01:15:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 1,257 bytes |
コンパイル時間 | 2,166 ms |
コンパイル使用メモリ | 203,412 KB |
最終ジャッジ日時 | 2025-01-28 20:52:09 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long constexpr int inf = 1e18; constexpr int maxn = 2e5 + 5; constexpr int mod = 998244353; inline vector<int> calc(string &s, string &t) { int n = (int)s.size(); vector<int> res(n + 1); int c = 0; for (int i = 0; i < n; i ++) { if (s[i] == t[c]) c ++; res[i + 1] = c; } return res; } inline void solve() { int n, m, ans = 0; cin >> n >> m; vector<string> s(n); for (auto &x : s) cin >> x; vector x(n - 1, vector<int>()), y(x); for (int i = 0; i < n - 1; i ++) x[i] = calc(s[0], s[i + 1]); for (auto &x : s) reverse(x.begin(), x.end()); for (int i = 0; i < n - 1; i ++) y[i] = calc(s[0], s[i + 1]); for (auto &x : s) reverse(x.begin(), x.end()); for (int i = 0; i <= m; i ++) { for (int j = 0; j < 26; j ++) { if (i != m && s[0][i] == 'a' + j) continue; int f = 1; for (int k = 0; k < n - 1; k ++) if (x[k][i] + y[k][m - i] < m - 1 || s[k + 1][x[k][i]] != 'a' + j) { f = 0; break; } ans += f; } } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; } /* The details you should care: */