QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187135#3010. Subsequences in SubstringsSolitaryDream#AC ✓30ms14092kbC++14675b2023-09-24 14:51:052023-09-24 14:51:05

Judging History

你现在查看的是最新测评结果

  • [2023-09-24 14:51:05]
  • 评测
  • 测评结果:AC
  • 用时:30ms
  • 内存:14092kb
  • [2023-09-24 14:51:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char s[N], t[N];
int ne[N][26];
int n, m;
int main() {
    scanf("%s%s", s + 1, t + 1);
    n = strlen(s + 1); 
    m = strlen(t + 1);
    for (int d = 0; d < 26; ++d) ne[n + 1][d] = n + 1;
    for (int i = n; i; --i) {
        memcpy(ne[i], ne[i + 1], sizeof ne[i]);
        ne[i][s[i] - 'a'] = i;
    }
    long long ans = 0;
    for (int i = n; i; --i) {
        int cur = i - 1;
        for (int j = 1; j <= m && cur != n + 1; ++j) cur = ne[cur + 1][t[j] - 'a'];
        // printf("%d %d\n", i, cur);
        ans += n + 1 - cur;
    }
    printf("%lld\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 13976kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

5000050000

result:

ok answer is '5000050000'

Test #2:

score: 0
Accepted
time: 30ms
memory: 13820kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

4990154851

result:

ok answer is '4990154851'

Test #3:

score: 0
Accepted
time: 0ms
memory: 13872kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

99999

result:

ok answer is '99999'

Test #4:

score: 0
Accepted
time: 4ms
memory: 13924kb

input:

zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

99999

result:

ok answer is '99999'

Test #5:

score: 0
Accepted
time: 0ms
memory: 14056kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

25000000

result:

ok answer is '25000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 13924kb

input:

abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd...

output:

4999600009

result:

ok answer is '4999600009'

Test #7:

score: 0
Accepted
time: 13ms
memory: 11232kb

input:

abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...

output:

2141234561

result:

ok answer is '2141234561'

Test #8:

score: 0
Accepted
time: 30ms
memory: 14092kb

input:

wihvaaqgcpykasskatdribceiwzsmjjuuqjononjknibpawvqtqeumefxkhoafyndgpipsfjxjhbqbfyqsjudqbuimewxmleojthsptiasfdgjtebxiawijflvdxvzohzedotgapzauzimqcjsgrziissrndyglcfftnnlpaoyxkzejlobssdkcbxpipvyebemirndverdgdvvgkdcejuousanpxxkhdtwwmblqmwcyalthjmuynwmxaponazdazeazztkeoxdhhesxdqelnywvqdlcmstmfullktqtvmlsu...

output:

4742431461

result:

ok answer is '4742431461'

Test #9:

score: 0
Accepted
time: 22ms
memory: 13868kb

input:

amplpsqzijrsvjngzzeidkopdzrakreyesiklovfcymebhprmsbrghdljejpizhnzbtsnjfczwlqyytmzjejfxetvjgzzjtsqbpownodtmvakxtqwwklkwuukuqhnwjxakmqgwulsfxzyyhvzsngeclgqmmxonaizvajzgmehgzucqoydxjxuaoctjmarsubzhjkudquwlkefsyutcwhywbvyhbrpccsoswijledgxonogqiwewskgdaxuibtbhjblycupocgvxoyhoeulnzsbyvvwluswwxfrebjuylmeov...

output:

4744748626

result:

ok answer is '4744748626'

Test #10:

score: 0
Accepted
time: 27ms
memory: 13868kb

input:

byqhmrogmrkrkxlopxzyrphkqoflakhnkpjdvojgpwfxndlvuxhjjdsuwudjjpgldwbcuqgffvsgdcykrrqxilxuclgoecxabivddsgyesxorzdgnydiiuhfoestiuyckxovcmuporhstqntgkxfdqrqdhremdaqgmyiuhbcvtfaunwpgkhqapzpfnpqhxxllmptxoueguozeluzxksmzaqnhvjikgvwkjkztqrkpplizyoshavxpnfwbynwquhzushxwckftjvveazomjbyibhynxphhicasishegoxitjo...

output:

4741244687

result:

ok answer is '4741244687'

Test #11:

score: 0
Accepted
time: 0ms
memory: 13924kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

3887366754

result:

ok answer is '3887366754'

Test #12:

score: 0
Accepted
time: 4ms
memory: 13876kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

aaacccabababacccccbbccaaaaabcacabaaccabccabcacbbccabbbacccabaaaacabbcbaccbabbccaccbcaabcacbaccabcaabcccaaabcabcabccbabcccabbaaccbaccacbcabacccbabacacbabaccaaababababaacbacbaacabbcbcbccccaaaacabcabbbcb
caabc

output:

17714

result:

ok answer is '17714'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4052kb

input:

acbdccaaacdbdbccccdddaddbdcbbdbbbadaacbbaddcdbcacaadcddcbdabdbdacadaadbbccaaacbdccabbbaabcbdcbabcdcadaacbdbbddbcccbdbcabacaadddbcaadbcacbdbccccacdddaaacccdddacbbabccbbcacbbbabdcbaddcbddadbbdcdcbcdcabdbdbdacdbabacdbdbcdcdbdcadbbcbbaacddccccdddbbcabcdddccbbdcbcdbdbdcddbdcbcbbbbdccccbbdabdcbbbdabcbbcbc...

output:

1923795

result:

ok answer is '1923795'

Test #15:

score: 0
Accepted
time: 4ms
memory: 6620kb

input:

dcdcaabcbbacccbaacacdeacaaadcdecaeeceecabeecadbdabbcabbadcaaedbcdeabddccdbbcaadabecdcabdebaeacdbccaebadaacdbdedccdcccbcbbeedbaeeabdecccabcbbaaacbcaeeadedeebbdeeebeacdcaddeabddaeedbbdaeeddeaedaeaaeacdceabceaeaceeecacdecdcadceceacdacccdeacdceededaeaadcdcdebbeaacaccccbbcbebddadaaecbabdaedcaabdacccbbdae...

output:

45098892

result:

ok answer is '45098892'

Test #16:

score: 0
Accepted
time: 8ms
memory: 8072kb

input:

haggcbhhacdahgcacdhcgehgcfcecffgecaaeggadfgbgdeedffafhecccgegbagcbahebhaaaaaahbgccffagbggdbcedgbhfaacefcdheabeefghdfdfabcbhhbaeefdbgaaahcfdhfeacgfbehbdhfdehaagfgfgehcdbadecbchgbadaadeaaabgafccaceadhdadhhhadfbddhddfceebbfgcgehdchhbgcfhedafgaebhgbfgdhcdbdbeebcahgfdfefhbcbhdddaadacbhgeahfhcddecfedaeebb...

output:

292904504

result:

ok answer is '292904504'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

aabb
ab

output:

4

result:

ok answer is '4'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

aabb
ba

output:

0

result:

ok answer is '0'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

abcdabcd
ac

output:

14

result:

ok answer is '14'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

abcdefghijklmnopqrstuvwxyz
z

output:

26

result:

ok answer is '26'

Test #21:

score: 0
Accepted
time: 1ms
memory: 5768kb

input:

abcdefghijklmnopqrstuvwxyz
za

output:

0

result:

ok answer is '0'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

a
a

output:

1

result:

ok answer is '1'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

abcdefg
abcdefg

output:

1

result:

ok answer is '1'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

pp
p

output:

3

result:

ok answer is '3'