Submission #74699370

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
#define endl '\n';

void solveA () {
  vector<int> month = {1, 3, 5, 7, 9};
  vector<int> date = {7, 3, 5, 7, 9};
  int d, w;
  cin >> d >> w;
  for (int i = 0; i < (int)date.size(); i ++) {
    if (d == month[i] && w == date[i]) {
      cout << "Yes" << endl;
      return;
    }
  }
  cout << "No" << endl;
}

void solveB () {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < m; j ++) {
      if (i == 0 || i == n - 1  || j == 0 || j == m - 1) cout << '#';
      else cout << ".";
    }
    cout << endl;
  }
}

void solveC () {
  int n;
  cin >> n;
  auto ok = vector(11, vector(11, vector<bool> (128, 0)));
  vector<pii> need(n);
  for (auto& [len, idx] : need) cin >> len >> idx;
  int m;
  cin >> m;
  vector<string> s(m);
  for (auto& str : s) cin >> str;
  for (int i = 0; i < m; i ++) {
    int k = s[i].size();
    for (int j = 0; j < k; j ++) {
      ok[k][j + 1][s[i][j]] = 1;
    }
  }
  for (int i = 0; i < m; i ++) {
    if ((int)s[i].size() != n) {
      cout << "No" << endl;
      continue;
    }
    bool flag = true;
   for (int j = 0; j < n; j ++) {
    auto& [len, idx] = need[j];
    if (ok[len][idx][s[i][j]] == 0) {
      cout << "No" << endl;
      flag = false;
      break;
    }
   }
   if (flag) cout << "Yes" << endl;
  }
}

void solveD () {
  string s, t;
  cin >> s >> t;
  int n = s.size();
  int m = t.size();
  vector<vector<int>> next_pos(n + 1, vector<int> (26, -1));
  for (int i = n - 1; i >= 0; i --) {
   next_pos[i] = next_pos[i + 1];
   next_pos[i][s[i] - 'a'] = i;
  }
  i64 ans = 0;
  for (int i = 0; i < n; i ++) {
    int t_ptr = 0;
    int j = i;
    while (t_ptr < m && j != -1) {
      int x = j;
      if (t_ptr != 0) x = j + 1;
      j = next_pos[x][t[t_ptr] - 'a'];
      t_ptr ++;
    }
    if (j == -1) ans += n - i;
    else if (t_ptr == m) ans += j - i;
  }
  cout << ans << endl;
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  solveD();
}

Submission Info

Judge Result