提出 #74669137
ソースコード 拡げる
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>
#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
#define int int64_t
using namespace std;
// /\_/\
// (= ._.)
// / > \>
// encouraging cat
const int INF = 10000000000000000;
//const int mod = 1000000007;
const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
signed main()
{
string s,t;
cin >> s >> t;
int n = s.size(), m = t.size();
vector<vector<int>> nxt(n, vector<int> (27, n));
vector<int> p(27, n);
for (int i = n - 1;i >= 0;i--)
{
nxt[i] = p;
p[s[i] - 'a'] = i;
}
int res = 0;
for (int i = 0;i < n;i++)
{
int ptr = i;
int cnt = 0;
if (s[i] == t[0])
{
cnt++;
}
for (int j = cnt;j < m;j++)
{
ptr = nxt[ptr][t[j] - 'a'];
if (ptr == n)
{
break;
}
}
res += ptr - i;
}
cout << res << '\n';
return 0;
}
提出情報
| 提出日時 | |
|---|---|
| 問題 | D - No-Subsequence Substring |
| ユーザ | litvinas |
| 言語 | C++23 (GCC 15.2.0) |
| 得点 | 400 |
| コード長 | 1610 Byte |
| 結果 | AC |
| 実行時間 | 66 ms |
| メモリ | 52084 KiB |
コンパイルエラー
./Main.cpp:32:1: warning: multi-line comment [-Wcomment]
32 | // /\_/\
| ^
ジャッジ結果
| セット名 | Sample | All | ||||
|---|---|---|---|---|---|---|
| 得点 / 配点 | 0 / 0 | 400 / 400 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| Sample | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt |
| All | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt |
| ケース名 | 結果 | 実行時間 | メモリ |
|---|---|---|---|
| 00_sample_00.txt | AC | 1 ms | 3492 KiB |
| 00_sample_01.txt | AC | 1 ms | 3620 KiB |
| 00_sample_02.txt | AC | 1 ms | 3464 KiB |
| 01_random_03.txt | AC | 30 ms | 33432 KiB |
| 01_random_04.txt | AC | 35 ms | 35188 KiB |
| 01_random_05.txt | AC | 15 ms | 20552 KiB |
| 01_random_06.txt | AC | 18 ms | 19452 KiB |
| 01_random_07.txt | AC | 21 ms | 28284 KiB |
| 01_random_08.txt | AC | 50 ms | 52028 KiB |
| 01_random_09.txt | AC | 54 ms | 52036 KiB |
| 01_random_10.txt | AC | 49 ms | 51848 KiB |
| 01_random_11.txt | AC | 62 ms | 52040 KiB |
| 01_random_12.txt | AC | 34 ms | 51892 KiB |
| 01_random_13.txt | AC | 35 ms | 51912 KiB |
| 01_random_14.txt | AC | 48 ms | 51824 KiB |
| 01_random_15.txt | AC | 57 ms | 51836 KiB |
| 01_random_16.txt | AC | 58 ms | 51836 KiB |
| 01_random_17.txt | AC | 53 ms | 51892 KiB |
| 01_random_18.txt | AC | 34 ms | 51840 KiB |
| 01_random_19.txt | AC | 61 ms | 51836 KiB |
| 01_random_20.txt | AC | 58 ms | 51956 KiB |
| 01_random_21.txt | AC | 36 ms | 51840 KiB |
| 01_random_22.txt | AC | 60 ms | 51836 KiB |
| 01_random_23.txt | AC | 65 ms | 51888 KiB |
| 01_random_24.txt | AC | 57 ms | 51856 KiB |
| 01_random_25.txt | AC | 66 ms | 52084 KiB |
| 01_random_26.txt | AC | 45 ms | 51892 KiB |
| 01_random_27.txt | AC | 53 ms | 51840 KiB |
| 01_random_28.txt | AC | 56 ms | 52084 KiB |
| 01_random_29.txt | AC | 50 ms | 51888 KiB |
| 01_random_30.txt | AC | 47 ms | 52012 KiB |
| 01_random_31.txt | AC | 43 ms | 52040 KiB |
| 01_random_32.txt | AC | 31 ms | 51896 KiB |
| 01_random_33.txt | AC | 52 ms | 52084 KiB |
| 01_random_34.txt | AC | 47 ms | 51840 KiB |
| 01_random_35.txt | AC | 55 ms | 51888 KiB |
| 01_random_36.txt | AC | 51 ms | 51840 KiB |
| 01_random_37.txt | AC | 45 ms | 52036 KiB |
| 01_random_38.txt | AC | 45 ms | 51888 KiB |
| 01_random_39.txt | AC | 43 ms | 51836 KiB |
| 01_random_40.txt | AC | 34 ms | 46904 KiB |
| 01_random_41.txt | AC | 40 ms | 41856 KiB |
| 01_random_42.txt | AC | 44 ms | 45100 KiB |
| 01_random_43.txt | AC | 12 ms | 18172 KiB |
| 01_random_44.txt | AC | 34 ms | 38524 KiB |
| 01_random_45.txt | AC | 9 ms | 12076 KiB |
| 01_random_46.txt | AC | 47 ms | 45064 KiB |
| 01_random_47.txt | AC | 26 ms | 26172 KiB |
| 01_random_48.txt | AC | 9 ms | 18456 KiB |
| 01_random_49.txt | AC | 31 ms | 35072 KiB |
| 01_random_50.txt | AC | 27 ms | 43468 KiB |
| 01_random_51.txt | AC | 55 ms | 51956 KiB |
| 01_random_52.txt | AC | 30 ms | 51840 KiB |
| 01_random_53.txt | AC | 1 ms | 3468 KiB |
| 01_random_54.txt | AC | 1 ms | 3528 KiB |
| 01_random_55.txt | AC | 1 ms | 3528 KiB |