XMU 1431 字符串的演算 字符串的的次方中的子串中找 目标串

XMU 1431 字符串的运算 字符串的的次方中的子串中找 目标串

/*以下解题报告来自同学 不是我搞的 
题目：字符串的运算题目连接：http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1431题目大意：我们对字符串 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))。*/

#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;}