QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108937#3010. Subsequences in SubstringsidontreallyknowAC ✓37ms14152kbC++17978b2023-05-27 03:59:402023-05-27 03:59:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-27 03:59:44]
  • 评测
  • 测评结果:AC
  • 用时:37ms
  • 内存:14152kb
  • [2023-05-27 03:59:40]
  • 提交

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'