11/5/2018模拟 Problem C-白红宇

11/5/2018模拟 Problem C

阅读量：6258 次

发布时间：2019-06-22

本文共 1333 字，大约阅读时间需要 4 分钟。

题面

题解

~~我有特殊的哈希技巧~~

以到下一个相同字符的距离为值哈希, 如果不存在或在串外, 就是 \(|T| + 1\).

加入一个新字符 \(S_i\) 时, 同时修改它上一次出现时的值, 由 \(|T| + 1\) 修改为 \(i\).

详见代码.

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;#define rep(i,l,r) for(register int i=(l);i<=(r);++i)#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)#define il inlinetypedef double db;typedef long long ll;typedef unsigned long long ull;//---------------------------------------const int nsz=1e6+50,msz=1e5+50,base=1e5+3;int n,m;char s[nsz],t[msz];il int tr(char c){return c-'a'+1;}int nes[nsz],prs[nsz];int net[msz],prt[msz];ull hs=0,ht=0,pb[msz]{1};void gene(char *s,int *ne,int *pr,int n){ static int bot[30]; rep(i,1,26)bot[i]=n+1; repdo(i,n,1){ ne[i]=bot[tr(s[i-1])]; bot[tr(s[i-1])]=i; } rep(i,1,26)bot[i]=0; rep(i,1,n){ pr[i]=bot[tr(s[i-1])]; bot[tr(s[i-1])]=i; }}void sol(){ gene(s,nes,prs,n); gene(t,net,prt,m); rep(i,1,m){ ht=ht*base+(net[i]==m+1?m+1:net[i]-i); hs=hs*base+(nes[i]>m?m+1:nes[i]-i); pb[i]=pb[i-1]*base; } if(hs==ht)cout<<1<<'\n'; ull tmp; rep(i,m+1,n){//[i-m+1,i] tmp=(nes[i-m]>i-1?m+1:nes[i-m]-(i-m)); hs=hs*base-tmp*pb[m]; tmp=i-prs[i]; if(tmp
           
            >s>>t; n=strlen(s),m=strlen(t); if(n