NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #197041 | #2723. 8.3t1 | wosile | 100 | 41ms | 5020kb | C++ | 716b | 2023-11-05 11:25:39 | 2023-11-05 12:08:42 |
answer
#include<bits/stdc++.h>
using namespace std;
int T;
int nxt[100005][30];
char s[100005],t[100005];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
scanf("%s",t+1);
int ls=strlen(s+1),lt=strlen(t+1);
for(int i=0;i<26;i++)nxt[ls][i]=0;
for(int i=ls;i>=1;i--){
for(int j=0;j<26;j++)nxt[i-1][j]=nxt[i][j];
nxt[i-1][s[i]-'a']=i;
}
int cur=0,ans=1;
for(int i=1;i<=lt;i++){
int c=t[i]-'a';
// printf("%d %d\n",cur,nxt[cur][c]);
if(nxt[cur][c]==0){
if(nxt[0][c]){
ans++;
cur=nxt[0][c];
}
else{
ans=-1;
break;
}
}
else cur=nxt[cur][c];
}
printf("%d\n",ans);
}
return 0;
//quod erat demonstrandum
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 1212kb
input:
10 sebgiuoczoemigefvlahqucwozknojbavqvroalawgbeyyxqro sduzprlgvftflmhvwxgzlizgvtikoudnhjulnacqwjcazr...
output:
-1 15 -1 -1 1 -1 -1 6 -1 1
result:
ok 10 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 1208kb
input:
10 qcyhppilxfzyhtxnhvvhdlaheytuppmeuonogsfumadymhmxrberabkedocjpuszituknqbgkhsiqaevo fkanwvqepspitbd...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 10 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 1212kb
input:
10 juphrputzg bkujvwsakuvwbshnbpcyukppchdhlwztffjngot ixlwahqcxtbnhjslellyrzfelfdtltpsvjmbimhuytxmcr...
output:
-1 4 -1 -1 -1 -1 18 -1 -1 -1
result:
ok 10 lines
Test #4:
score: 10
Accepted
time: 8ms
memory: 4308kb
input:
10 ttuqemikgpxkeymjlgseiojuqswwmznssmxyfnjaskakyxyexvsczxfqatmfhutjguengtfjuwunlgfxfkohwwghdfoqsplxe...
output:
26 37 36 32 60 50 36 7 12 7
result:
ok 10 lines
Test #5:
score: 10
Accepted
time: 9ms
memory: 5020kb
input:
10 zoszzoigfwwlfbkydwdcqloxdkskwhvojdjrqiwnrubsvykquywsrilgzqznzllkhzzjfwqlguvqumzbxgfmwfujsctbjjiks...
output:
22 6 29 38 48 12 25 34 27 32
result:
ok 10 lines
Test #6:
score: 10
Accepted
time: 6ms
memory: 4456kb
input:
10 tqooqroiawdbsqcnkrdpfgmuyzdsvufrrddkwjvjnnutilolejncyozrivccpmgkmxmsotxvrnjuosgtwjnvtmgygofvyywqm...
output:
149 13 67 16 16 11 33 39 15 30
result:
ok 10 lines
Test #7:
score: 10
Accepted
time: 6ms
memory: 4024kb
input:
10 liearkjhuusscmcwvvqkahoeaffwqaljknpzkigdlnllujcdtcnptzrijnxbbcgwcyojliircpyqkzstvmaggdjtfnqwoicml...
output:
19 13 35 5 31 13 31 27 11 19
result:
ok 10 lines
Test #8:
score: 10
Accepted
time: 4ms
memory: 4396kb
input:
10 kymwlbunfqaqmckjntfjgnrnvbekdsxtcpjvrepszyfbbeyxlyjhupiymdyyvrjexvuvmtskmmmmduzxkrosqenivlewnyyye...
output:
42 124 16 22 25 39 23 2 20 17
result:
ok 10 lines
Test #9:
score: 10
Accepted
time: 7ms
memory: 4976kb
input:
10 efzblaborigjcizqghvncfiuafstlfpqzdvjbafmizzijqzximreaqldfuhrrrwrrydpguhghgqewnmsniepiiaunnbbbbmyy...
output:
13 4 13 24 1 45 107 22 72 260
result:
ok 10 lines
Test #10:
score: 10
Accepted
time: 0ms
memory: 4608kb
input:
10 nlsfflwmguzcxupjoouzcerebughnqovfuwahtthulmiffgzcrlhnzqjutlaguhtydqfhetimspvnlzijtfvdsqeykpnnflku...
output:
280 15 38 11 215 28 107 66 5 3
result:
ok 10 lines
