XMU 1431 字符串的运算 字符串的的次方中的子串中找 目标串
1431.字符串的运算
Time Limit: 1500 MS Memory Limit: 65536 K
Total Submissions: 137 (36 users) Accepted: 36 (26 users)
Description
我们对字符串 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)
Input
输入只有2行, 分别为字符串S和T (1 <= |S|, |T| <= 100,000), 输入保证字符串S和T只由小写字母构成。
Output
输出最小的k, 满足T ∈Subsequence(S ^ k), 若不存在这样的k, 则输出-1
Sample Input
abc
abacbc
Sample Output
3
Source
doraemon @ xmu
[ Submit] [ Statistic] [ Status ] [ Discuss]
All Copyright Reserved 2007 Xiang Guangte, Zheng Le
Xmu.Csd All Rights Reserved.
/*以下解题报告来自同学 不是我搞的
题目：字符串的运算
题目大意：
我们对字符串 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)
解题思路：Subsequence(S)就是从S中选一些字符保持相对顺序不变组成的非空字符串；
现在我们要把T分成K份这样的字符串，K越小越好，于是策略就是：先令k=0，在串S中找串T，从串T的第一个字符找起
遇到了第一个字符再找第二个字符，一直找到不能找为止，然后k++，然后我们又返回到S串的开始位置继续找，直到把
T中的所有字符都找完，最后的答案就是k,如果T中出现了S中没有的字符，那么这个字符是永远找不到的，最后答案就是-1;
但是暴力枚举S串的下标时间复杂度是O(N^2)，会超时，如果可以在S中找T的字符时快速定位，这样就不会超时了，因此
可以先预处理一下S串，建立S串中每个字符的在S中出现的序列，比如字符'a'在S串中1,3,5位置出现过，那么字符'a'的序列
就是(1,3,5)。有了这个序列后我们就可以快速定位一个我们想找的字符了，比如现在在S的i位置，我要找的下一个字符是
'a',那么我们就用i+1下标在字符'a'的序列中二分找到最接近下标，如果没有我们就直接返回S串的开始位置，继续用上述的
方法，这样时间复杂度就是降为O(N*log(N))。
*/
[cpp]
#include<stdio.h>
#include<string.h>
#include<set>
using namespace std;
int vis[30];
char s[110000],t[110000];
int find(int n,int m)
{
int i,j=0,k=0,b;
set <int> next[30];
set <int> ::iterator it;
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
vis[s[i]-'a']=1,next[s[i]-'a'].insert(i);
for(i=0;i<m;i++) if(!vis[t[i]-'a']) return -1;
i=0;
/*
abc n=3
abacbc m=6
*/
while(j<m)
{
while(j<m)
{
b=t[j]-'a';
it=next[b].lower_bound(i);//next里面存的是数组的下标
/*函数lower_bound()在first和last中的前闭后开区间进行二分查找，
返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置*/
if(it==next[b].end())//没有找到比i大的下一个b的话
{
if(i==0) return -1;//如果从第1个开始找都木有找到b字符那说明不存在
i=0; break;//没有找到比i大的下一个b 新增加一个s串从开头继续找
}
else i=(*it)+1,j++;//i前进到 *it对应的下标的下一个
}
k++;
}
return k;
}
int main()
{
int i,j,n,m,flag;
while(scanf("%s%s",s,t)!=EOF)
{
n=strlen(s);
m=strlen(t);
printf("%d\n",find(n,m));
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<set>
using namespace std;
int vis[30];
char s[110000],t[110000];
int find(int n,int m)
{
int i,j=0,k=0,b;
set <int> next[30];
set <int> ::iterator it;
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
vis[s[i]-'a']=1,next[s[i]-'a'].insert(i);
for(i=0;i<m;i++) if(!vis[t[i]-'a']) return -1;
i=0;
/*
abc n=3
abacbc m=6
*/
while(j<m)
{
while(j<m)
{
b=t[j]-'a';
it=next[b].lower_bound(i);//next里面存的是数组的下标
/*函数lower_bound()在first和last中的前闭后开区间进行二分查找，
返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置*/
&nb
补充：综合编程 , 其他综合 ,
