ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197046 | #2723. 8.3t1 | snow_trace | 100 | 145ms | 5032kb | C++11 | 1.3kb | 2023-11-05 11:32:49 | 2023-11-05 12:09:04 |
answer
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define endl '\n'
int t;
char s1[200005],s2[200005];
int n,m;
int nxt[200005][26];
int tong1[30],tong2[30];
vector<int>pos[30];
void solve(){
scanf("%s",s1+1);scanf("%s",s2+1);
n = strlen(s1+1),m = strlen(s2+1);
memset(tong1,0,sizeof(tong1));memset(tong2,0,sizeof(tong2));
for(int i =0;i<=26;i++)pos[i].clear();
for(int i = 1;i<=n;i++)tong1[s1[i]-'a']++;
for(int i = 1;i<=m;i++)tong2[s2[i]-'a']++;
for(int i = 0;i<26;i++){
if(tong2[i] and tong1[i] == 0){
cout << -1 << '\n';return;
}
}for(int i = 1;i<=n;i++)s1[i+n] = s1[i];
for(int i= 0;i<26;i++)pos[i].push_back(1);
for(int i = 1;i<=2*n;i++)pos[s1[i]-'a'].push_back(i);
for(int i =0;i<26;i++)pos[i].push_back(2*n+1);
// cout << 111 << endl;
for(int i =0;i<26;i++){
for(int j = 0;j+1<pos[i].size();j++){
for(int k = pos[i][j];k<min(pos[i][j+1],n+1);k++){
// cout << i << " " << j << " " << k << endl;
nxt[k][i] = pos[i][j+1];
}
}
}//cout << 111 << endl;
int ans = 1,now = pos[s2[1]-'a'][1];
//cout << now << endl;
for(int i = 2;i<=m;i++){
int nt = nxt[now][s2[i]-'a'];
// cout << nt << endl;
if(nt>n)nt-=n,ans++;now = nt;
}cout << ans << endl;
}
signed main(){
cin >> t;
while(t--){
solve();
}
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1296kb
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: 1240kb
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: 1300kb
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: 20ms
memory: 4304kb
input:
10 ttuqemikgpxkeymjlgseiojuqswwmznssmxyfnjaskakyxyexvsczxfqatmfhutjguengtfjuwunlgfxfkohwwghdfoqsplxe...
output:
26 37 36 32 60 50 36 7 12 7
result:
ok 10 lines
Test #5:
score: 10
Accepted
time: 24ms
memory: 5032kb
input:
10 zoszzoigfwwlfbkydwdcqloxdkskwhvojdjrqiwnrubsvykquywsrilgzqznzllkhzzjfwqlguvqumzbxgfmwfujsctbjjiks...
output:
22 6 29 38 48 12 25 34 27 32
result:
ok 10 lines
Test #6:
score: 10
Accepted
time: 20ms
memory: 4496kb
input:
10 tqooqroiawdbsqcnkrdpfgmuyzdsvufrrddkwjvjnnutilolejncyozrivccpmgkmxmsotxvrnjuosgtwjnvtmgygofvyywqm...
output:
149 13 67 16 16 11 33 39 15 30
result:
ok 10 lines
Test #7:
score: 10
Accepted
time: 23ms
memory: 3968kb
input:
10 liearkjhuusscmcwvvqkahoeaffwqaljknpzkigdlnllujcdtcnptzrijnxbbcgwcyojliircpyqkzstvmaggdjtfnqwoicml...
output:
19 13 35 5 31 13 31 27 11 19
result:
ok 10 lines
Test #8:
score: 10
Accepted
time: 18ms
memory: 4460kb
input:
10 kymwlbunfqaqmckjntfjgnrnvbekdsxtcpjvrepszyfbbeyxlyjhupiymdyyvrjexvuvmtskmmmmduzxkrosqenivlewnyyye...
output:
42 124 16 22 25 39 23 2 20 17
result:
ok 10 lines
Test #9:
score: 10
Accepted
time: 21ms
memory: 4756kb
input:
10 efzblaborigjcizqghvncfiuafstlfpqzdvjbafmizzijqzximreaqldfuhrrrwrrydpguhghgqewnmsniepiiaunnbbbbmyy...
output:
13 4 13 24 1 45 107 22 72 260
result:
ok 10 lines
Test #10:
score: 10
Accepted
time: 19ms
memory: 4548kb
input:
10 nlsfflwmguzcxupjoouzcerebughnqovfuwahtthulmiffgzcrlhnzqjutlaguhtydqfhetimspvnlzijtfvdsqeykpnnflku...
output:
280 15 38 11 215 28 107 66 5 3
result:
ok 10 lines