UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197046#2723. 8.3t1snow_trace100145ms5032kbC++111.3kb2023-11-05 11:32:492023-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