QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108937 | #3010. Subsequences in Substrings | idontreallyknow | AC ✓ | 37ms | 14152kb | C++17 | 978b | 2023-05-27 03:59:40 | 2023-05-27 03:59:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5+5;
int nxt[mx][26], le[mx];
int main() {
string s,t;
cin >> s >> t;
int n = s.size();
memset(nxt,-1,sizeof(nxt));
memset(le,-1,sizeof(le));
for (int i = 0; i < n; i++) {
if (i > 0) {
for (int j = 0; j < 26; j++) {
nxt[i][j] = nxt[i-1][j];
}
}
nxt[i][s[i]-'a'] = i;
}
for (int i = 0; i < n; i++) {
int cur = i;
for (int j = t.size()-1; j >= 0; j--) {
if (cur < 0) {
break;
}
cur = nxt[cur][t[j]-'a'];
if (j != 0) {
cur--;
}
}
if (cur >= 0) {
le[i] = cur;
}
}
long long ans = 0;
for (int i = 0; i < n; i++) {
if (le[i] != -1) {
ans += le[i]+1;
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14016kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
5000050000
result:
ok answer is '5000050000'
Test #2:
score: 0
Accepted
time: 37ms
memory: 14012kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
4990154851
result:
ok answer is '4990154851'
Test #3:
score: 0
Accepted
time: 6ms
memory: 14108kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #4:
score: 0
Accepted
time: 14ms
memory: 14140kb
input:
zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #5:
score: 0
Accepted
time: 12ms
memory: 14140kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
25000000
result:
ok answer is '25000000'
Test #6:
score: 0
Accepted
time: 3ms
memory: 14112kb
input:
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd...
output:
4999600009
result:
ok answer is '4999600009'
Test #7:
score: 0
Accepted
time: 22ms
memory: 14092kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
2141234561
result:
ok answer is '2141234561'
Test #8:
score: 0
Accepted
time: 26ms
memory: 14144kb
input:
wihvaaqgcpykasskatdribceiwzsmjjuuqjononjknibpawvqtqeumefxkhoafyndgpipsfjxjhbqbfyqsjudqbuimewxmleojthsptiasfdgjtebxiawijflvdxvzohzedotgapzauzimqcjsgrziissrndyglcfftnnlpaoyxkzejlobssdkcbxpipvyebemirndverdgdvvgkdcejuousanpxxkhdtwwmblqmwcyalthjmuynwmxaponazdazeazztkeoxdhhesxdqelnywvqdlcmstmfullktqtvmlsu...
output:
4742431461
result:
ok answer is '4742431461'
Test #9:
score: 0
Accepted
time: 30ms
memory: 14012kb
input:
amplpsqzijrsvjngzzeidkopdzrakreyesiklovfcymebhprmsbrghdljejpizhnzbtsnjfczwlqyytmzjejfxetvjgzzjtsqbpownodtmvakxtqwwklkwuukuqhnwjxakmqgwulsfxzyyhvzsngeclgqmmxonaizvajzgmehgzucqoydxjxuaoctjmarsubzhjkudquwlkefsyutcwhywbvyhbrpccsoswijledgxonogqiwewskgdaxuibtbhjblycupocgvxoyhoeulnzsbyvvwluswwxfrebjuylmeov...
output:
4744748626
result:
ok answer is '4744748626'
Test #10:
score: 0
Accepted
time: 33ms
memory: 14056kb
input:
byqhmrogmrkrkxlopxzyrphkqoflakhnkpjdvojgpwfxndlvuxhjjdsuwudjjpgldwbcuqgffvsgdcykrrqxilxuclgoecxabivddsgyesxorzdgnydiiuhfoestiuyckxovcmuporhstqntgkxfdqrqdhremdaqgmyiuhbcvtfaunwpgkhqapzpfnpqhxxllmptxoueguozeluzxksmzaqnhvjikgvwkjkztqrkpplizyoshavxpnfwbynwquhzushxwckftjvveazomjbyibhynxphhicasishegoxitjo...
output:
4741244687
result:
ok answer is '4741244687'
Test #11:
score: 0
Accepted
time: 6ms
memory: 14032kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
3887366754
result:
ok answer is '3887366754'
Test #12:
score: 0
Accepted
time: 9ms
memory: 14152kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 5ms
memory: 13996kb
input:
aaacccabababacccccbbccaaaaabcacabaaccabccabcacbbccabbbacccabaaaacabbcbaccbabbccaccbcaabcacbaccabcaabcccaaabcabcabccbabcccabbaaccbaccacbcabacccbabacacbabaccaaababababaacbacbaacabbcbcbccccaaaacabcabbbcb caabc
output:
17714
result:
ok answer is '17714'
Test #14:
score: 0
Accepted
time: 4ms
memory: 14016kb
input:
acbdccaaacdbdbccccdddaddbdcbbdbbbadaacbbaddcdbcacaadcddcbdabdbdacadaadbbccaaacbdccabbbaabcbdcbabcdcadaacbdbbddbcccbdbcabacaadddbcaadbcacbdbccccacdddaaacccdddacbbabccbbcacbbbabdcbaddcbddadbbdcdcbcdcabdbdbdacdbabacdbdbcdcdbdcadbbcbbaacddccccdddbbcabcdddccbbdcbcdbdbdcddbdcbcbbbbdccccbbdabdcbbbdabcbbcbc...
output:
1923795
result:
ok answer is '1923795'
Test #15:
score: 0
Accepted
time: 6ms
memory: 13908kb
input:
dcdcaabcbbacccbaacacdeacaaadcdecaeeceecabeecadbdabbcabbadcaaedbcdeabddccdbbcaadabecdcabdebaeacdbccaebadaacdbdedccdcccbcbbeedbaeeabdecccabcbbaaacbcaeeadedeebbdeeebeacdcaddeabddaeedbbdaeeddeaedaeaaeacdceabceaeaceeecacdecdcadceceacdacccdeacdceededaeaadcdcdebbeaacaccccbbcbebddadaaecbabdaedcaabdacccbbdae...
output:
45098892
result:
ok answer is '45098892'
Test #16:
score: 0
Accepted
time: 13ms
memory: 13940kb
input:
haggcbhhacdahgcacdhcgehgcfcecffgecaaeggadfgbgdeedffafhecccgegbagcbahebhaaaaaahbgccffagbggdbcedgbhfaacefcdheabeefghdfdfabcbhhbaeefdbgaaahcfdhfeacgfbehbdhfdehaagfgfgehcdbadecbchgbadaadeaaabgafccaceadhdadhhhadfbddhddfceebbfgcgehdchhbgcfhedafgaebhgbfgdhcdbdbeebcahgfdfefhbcbhdddaadacbhgeahfhcddecfedaeebb...
output:
292904504
result:
ok answer is '292904504'
Test #17:
score: 0
Accepted
time: 4ms
memory: 13960kb
input:
aabb ab
output:
4
result:
ok answer is '4'
Test #18:
score: 0
Accepted
time: 1ms
memory: 13820kb
input:
aabb ba
output:
0
result:
ok answer is '0'
Test #19:
score: 0
Accepted
time: 0ms
memory: 14012kb
input:
abcdabcd ac
output:
14
result:
ok answer is '14'
Test #20:
score: 0
Accepted
time: 1ms
memory: 13992kb
input:
abcdefghijklmnopqrstuvwxyz z
output:
26
result:
ok answer is '26'
Test #21:
score: 0
Accepted
time: 1ms
memory: 13932kb
input:
abcdefghijklmnopqrstuvwxyz za
output:
0
result:
ok answer is '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 14004kb
input:
a a
output:
1
result:
ok answer is '1'
Test #23:
score: 0
Accepted
time: 4ms
memory: 13940kb
input:
abcdefg abcdefg
output:
1
result:
ok answer is '1'
Test #24:
score: 0
Accepted
time: 1ms
memory: 13972kb
input:
pp p
output:
3
result:
ok answer is '3'