大家好，又见面了，我是全栈君。
1543: 字符串的运算再现
题目描述
我们对字符串 S 做了以下定义:
1. S ^ k表示由k个字符串S构成的新字符串。 例如, S = “abc”, k = 3, 则S ^ k = “abcabcabc”
2. Subsequence(S) 表示由字符串S的所有非空子序列构成的字符串集合。例如, S = “abc”, 则Subsequence(S) = {“a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”}
现在, 给你2个字符串S和T, 希望你能找到最小的k, 满足T ∈Subsequence(S ^ k)
1. S ^ k表示由k个字符串S构成的新字符串。 例如, S = “abc”, k = 3, 则S ^ k = “abcabcabc”
2. Subsequence(S) 表示由字符串S的所有非空子序列构成的字符串集合。例如, S = “abc”, 则Subsequence(S) = {“a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”}
现在, 给你2个字符串S和T, 希望你能找到最小的k, 满足T ∈Subsequence(S ^ k)
输入
输入只有2行, 分别为字符串S和T (1 <= |S|, |T| <= 100,000), 输入保证字符串S和T只由小写字母构成。
输出
输出最小的k, 满足T ∈Subsequence(S ^ k), 若不存在这样的k, 则输出-1
样例输入
abc
abacbc
样例输出
3
#pragma GCC diagnostic error "-std=c++11" #include <bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #include <typeinfo> using namespace std; const int N = 100000 + 5; char s[N], t[N]; void Init(int * a, int n){ for(int i = 0; i < n; i++) a[i] = 0;} int Work(){ int lens = strlen(s), lent = strlen(t); set<int> next[26]; int vis[26]; Init(vis, 26); for(int i = 0 ; i < lens; i++) vis[s[i] - 'a'] = 1, next[s[i]-'a'].insert(i); for(int i = 0; i < lent; i++) if(!vis[t[i]-'a']) return -1; int cur = 0, k = 1; set<int>::iterator it; for(int i = 0; i < lent; i++){ int p = t[i] - 'a'; if((it = next[p].lower_bound(cur)) != next[p].end()) cur = (*it) + 1; else cur = 0, k++, i--; } return k; } int main(){ _ while(cin >> s >> t){ cout << Work() << endl; } }
转载于:https://www.cnblogs.com/Pretty9/p/7424087.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108210.html原文链接：https://javaforall.net
