QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #371967 | #3010. Subsequences in Substrings | InfinityNS# | AC ✓ | 35ms | 14180kb | C++14 | 553b | 2024-03-30 18:45:53 | 2024-03-30 18:45:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
char s[N],t[N];
int nxt[N][26];
int main(){
scanf("%s",s+1);
scanf("%s",t+1);
int n=strlen(s+1);
int m=strlen(t+1);
for(int i=0;i<26;i++)nxt[n+1][i]=n+1;
for(int i=n;i>=1;i--){
for(int j=0;j<26;j++)nxt[i][j]=nxt[i+1][j];
nxt[i][s[i]-'a']=i;
}
ll ans=0;
for(int i=1;i<=n;i++){
int now=i-1;
for(int j=1;j<=m;j++){
now=nxt[now+1][t[j]-'a'];
if(now>n)break;
}
ans+=n-now+1;
}
printf("%lld\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 14064kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
5000050000
result:
ok answer is '5000050000'
Test #2:
score: 0
Accepted
time: 32ms
memory: 14004kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
4990154851
result:
ok answer is '4990154851'
Test #3:
score: 0
Accepted
time: 0ms
memory: 14148kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #4:
score: 0
Accepted
time: 6ms
memory: 14176kb
input:
zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #5:
score: 0
Accepted
time: 3ms
memory: 14072kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
25000000
result:
ok answer is '25000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 14140kb
input:
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd...
output:
4999600009
result:
ok answer is '4999600009'
Test #7:
score: 0
Accepted
time: 9ms
memory: 10616kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
2141234561
result:
ok answer is '2141234561'
Test #8:
score: 0
Accepted
time: 35ms
memory: 14068kb
input:
wihvaaqgcpykasskatdribceiwzsmjjuuqjononjknibpawvqtqeumefxkhoafyndgpipsfjxjhbqbfyqsjudqbuimewxmleojthsptiasfdgjtebxiawijflvdxvzohzedotgapzauzimqcjsgrziissrndyglcfftnnlpaoyxkzejlobssdkcbxpipvyebemirndverdgdvvgkdcejuousanpxxkhdtwwmblqmwcyalthjmuynwmxaponazdazeazztkeoxdhhesxdqelnywvqdlcmstmfullktqtvmlsu...
output:
4742431461
result:
ok answer is '4742431461'
Test #9:
score: 0
Accepted
time: 35ms
memory: 14180kb
input:
amplpsqzijrsvjngzzeidkopdzrakreyesiklovfcymebhprmsbrghdljejpizhnzbtsnjfczwlqyytmzjejfxetvjgzzjtsqbpownodtmvakxtqwwklkwuukuqhnwjxakmqgwulsfxzyyhvzsngeclgqmmxonaizvajzgmehgzucqoydxjxuaoctjmarsubzhjkudquwlkefsyutcwhywbvyhbrpccsoswijledgxonogqiwewskgdaxuibtbhjblycupocgvxoyhoeulnzsbyvvwluswwxfrebjuylmeov...
output:
4744748626
result:
ok answer is '4744748626'
Test #10:
score: 0
Accepted
time: 27ms
memory: 14144kb
input:
byqhmrogmrkrkxlopxzyrphkqoflakhnkpjdvojgpwfxndlvuxhjjdsuwudjjpgldwbcuqgffvsgdcykrrqxilxuclgoecxabivddsgyesxorzdgnydiiuhfoestiuyckxovcmuporhstqntgkxfdqrqdhremdaqgmyiuhbcvtfaunwpgkhqapzpfnpqhxxllmptxoueguozeluzxksmzaqnhvjikgvwkjkztqrkpplizyoshavxpnfwbynwquhzushxwckftjvveazomjbyibhynxphhicasishegoxitjo...
output:
4741244687
result:
ok answer is '4741244687'
Test #11:
score: 0
Accepted
time: 6ms
memory: 14008kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
3887366754
result:
ok answer is '3887366754'
Test #12:
score: 0
Accepted
time: 3ms
memory: 14048kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
aaacccabababacccccbbccaaaaabcacabaaccabccabcacbbccabbbacccabaaaacabbcbaccbabbccaccbcaabcacbaccabcaabcccaaabcabcabccbabcccabbaaccbaccacbcabacccbabacacbabaccaaababababaacbacbaacabbcbcbccccaaaacabcabbbcb caabc
output:
17714
result:
ok answer is '17714'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
acbdccaaacdbdbccccdddaddbdcbbdbbbadaacbbaddcdbcacaadcddcbdabdbdacadaadbbccaaacbdccabbbaabcbdcbabcdcadaacbdbbddbcccbdbcabacaadddbcaadbcacbdbccccacdddaaacccdddacbbabccbbcacbbbabdcbaddcbddadbbdcdcbcdcabdbdbdacdbabacdbdbcdcdbdcadbbcbbaacddccccdddbbcabcdddccbbdcbcdbdbdcddbdcbcbbbbdccccbbdabdcbbbdabcbbcbc...
output:
1923795
result:
ok answer is '1923795'
Test #15:
score: 0
Accepted
time: 2ms
memory: 4880kb
input:
dcdcaabcbbacccbaacacdeacaaadcdecaeeceecabeecadbdabbcabbadcaaedbcdeabddccdbbcaadabecdcabdebaeacdbccaebadaacdbdedccdcccbcbbeedbaeeabdecccabcbbaaacbcaeeadedeebbdeeebeacdcaddeabddaeedbbdaeeddeaedaeaaeacdceabceaeaceeecacdecdcadceceacdacccdeacdceededaeaadcdcdebbeaacaccccbbcbebddadaaecbabdaedcaabdacccbbdae...
output:
45098892
result:
ok answer is '45098892'
Test #16:
score: 0
Accepted
time: 9ms
memory: 6452kb
input:
haggcbhhacdahgcacdhcgehgcfcecffgecaaeggadfgbgdeedffafhecccgegbagcbahebhaaaaaahbgccffagbggdbcedgbhfaacefcdheabeefghdfdfabcbhhbaeefdbgaaahcfdhfeacgfbehbdhfdehaagfgfgehcdbadecbchgbadaadeaaabgafccaceadhdadhhhadfbddhddfceebbfgcgehdchhbgcfhedafgaebhgbfgdhcdbdbeebcahgfdfefhbcbhdddaadacbhgeahfhcddecfedaeebb...
output:
292904504
result:
ok answer is '292904504'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
aabb ab
output:
4
result:
ok answer is '4'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
aabb ba
output:
0
result:
ok answer is '0'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
abcdabcd ac
output:
14
result:
ok answer is '14'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
abcdefghijklmnopqrstuvwxyz z
output:
26
result:
ok answer is '26'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
abcdefghijklmnopqrstuvwxyz za
output:
0
result:
ok answer is '0'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
a a
output:
1
result:
ok answer is '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
abcdefg abcdefg
output:
1
result:
ok answer is '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
pp p
output:
3
result:
ok answer is '3'