题解 字符串

题解 字符串

题目描述

题解与心路历程

这道题看完后秒想到哈希，仔细想了一会儿后算了下复杂度为$O(26nlog26)$应该能过。于是码了一波，

然后本地一开始跑$8s$。。开始卡常，发现把堆排序改成$sort$后立马变成了$1.8s$，惊了！垃圾堆排

然后觉得有点凉( O 2 O_2 O2​优化$0.3s$)，开始改转$KMP$，考虑对每个字符串转化，把每个字符改成当前位置与上一次出现

位置的差值，第一次出现为$0$,然后再直接$KMP$匹配。发现还是不对，因为可能匹配时转化后的 s i ≠ 0 s_i \not=0 si​​=0但

t i = 0 t_i=0 ti​=0,这种情况能继续匹配只会是 s i s_i si​上次出现的位置在当前匹配了的字符串的左端点左边时，因此我们再判断字符是否相同是

另外写一个$check$来判断即可，注意建立$fail$数组时也需要这么做。考完发现$OJ$开了 O 2 O_2 O2​,哈希也过了。

$\mathcal{C}ode$

$KMP$

/*******************************
Author:galaxy yr
LANG:C++
Created Time:2019年10月21日 星期一 08时07分16秒
*******************************/
#include
#include
#include
#include
#include
#define NOTEusing namespace std;const int maxn=1e6+10;
const int mod=998244353;
const int x=131;
int fail[maxn],a[maxn],b[maxn],lena,lenb,pre[27],last[maxn];
string s,t;bool check(int u,int v)
{if(u==b[v]) return true;if(!b[v] && u>=v) return true;return false;
}void get_fail()
{int k=0;for(int i=1;i<=lenb;i++){while(k>0 && !check(b[i],k))k=fail[k-1];if(check(b[i],k))k++;fail[i]=k;}
}void kmp()
{for(int i=0,j=0;i<=lena;i++){while(j && !check(a[i],j)) j=fail[j-1];if(check(a[i],j))j++;if(j==lenb+1){printf("%d\n",i-j+2); j=fail[j-1];}}
}int main()
{//freopen("str.in","r",stdin);//freopen("str.out","w",stdout);cin>>s>>t; lena=s.size()-1; lenb=t.size()-1;memset(pre,-1,sizeof pre);for(int i=0;i<=lena;i++){if(pre[s[i]-'a']!=-1)a[i]=i-pre[s[i]-'a'],last[i]=pre[s[i]-'a'];else a[i]=0;pre[s[i]-'a']=i;}memset(pre,-1,sizeof pre);for(int i=0;i<=lenb;i++){if(pre[t[i]-'a']!=-1)b[i]=i-pre[t[i]-'a'];elseb[i]=0;pre[t[i]-'a']=i;}get_fail();kmp();return 0;
}

哈希

/*******************************
Author:galaxy yr
LANG:C++
Created Time:2019年10月21日 星期一 08时07分16秒
*******************************/
#include
#include
#include
#include
#includeusing namespace std;struct edge{int to,next;edge(int a=0,int b=0):to(a),next(b){}
};struct Node{int id,loc;Node(int a=0,int b=0):id(a),loc(b){}bool operator<(const Node & p) const{return loc<p.loc;}
};const int maxn=1e6+10;
const int mod=998244353;
const int x=131;
int f[27],h,tot,g[30],num[27],head[27],cnt,len,cs[27],lens;
edge e[maxn<<1];
string s,t;inline void hash_t()
{g[0]=1;for(register int i=1;i<=27;i++) g[i]=1ll*g[i-1]*x%mod;for(register int i=1;i<=len;i++){if(!f[t[i]-'a']) f[t[i]-'a']=++tot;h=(h+1ll*i*g[f[t[i]-'a']]%mod)%mod;}
}inline void add(const int& u,const int& v)
{e[++cnt]=edge(v,head[u]);head[u]=cnt;
}int find(const int & x,const int & loc)
{for(register int &i=head[x];i;i=e[i].next)if(e[i].to>=loc)return e[i].to;return -1;
}int get_hash(const int& loc)
{static int cnt,h;static Node tmp[28];cnt=0;for(register int i=0;i<26;i++)if(cs[i])tmp[++cnt]=Node(i,find(i,loc));h=0;sort(tmp+1,tmp+cnt+1);for(register int i=1;i<=cnt;i++)h=(h+1ll*g[i]*num[tmp[i].id]%mod)%mod;return h;
}inline void hash_s()
{for(register int i=lens-1;i;i--)add(s[i]-'a',i);for(register int i=1;i<=len;i++){num[s[i]-'a']+=i;cs[s[i]-'a']++;}for(register int i=1;i+len-1<lens;i++){if(get_hash(i)==h) printf("%d\n",i);for(register int i=0;i<26;i++) num[i]-=cs[i];if(i+len<lens)num[s[i+len]-'a']+=len,cs[s[i+len]-'a']++;cs[s[i]-'a']--;}
}int main()
{//freopen("str.in","r",stdin);//freopen("str_hash.out","w",stdout);cin>>s>>t; len=t.size();s="#"+s,t="#"+t;lens=s.size();hash_t();hash_s();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！