bzoj 4598[Sdoi 2016]モード文字列hash+ポイント

1439 ワード

ハッシュにもテクニックがあります.さもないと間違いやすい.
マッチング列範囲は1 e 6なので,通常hash誤り確率も大きい.
だからマッチングの特性(長さはマッチング列に一つ一つ対応)を利用してhashをすると、エラー確率が小さくなり、hashチェーンに相当するでしょう.
最初に書かれた各接頭辞hash格納位置.このようなhashには1 e 6の値がある.
コード:

#include
#include
#include
#include
#include
#define P 2147483647
#define ll long long 
#define D(x) cout<v[N];
ll qian[N],hou[N];
int sz[N],fu[N],f[N],g[N],vf[N],vg[N],i,j,n,m,ans,tot,rt,now,T,a,b;
ll ci[N],lin;
char  ch[N],S[N];
bool vis[N];
void dfs(int o,int fa)
{
int i,nd;
    sz[o]=1;fu[o]=fa;
    for(i=0;i'Z')scanf("%c",&ch[i]);
        }
        for(i=1;i'Z')scanf("%c",&S[i]);
        }
lin=0;
for(i=0;i<=n;i++)
{
        lin=(lin*27+1ll*(S[(i%m)+1]-'A'+1))%P;
        qian[i]=lin;    
}
lin=0;
for(i=0;i<=n;i++)
{
        lin=(lin*27+1ll*(S[(m-i%m-1)+1]-'A'+1))%P;
        hou[i]=lin;
}       
        dfs(1,0);
        tot=n;
        zzx(1,0);   dfs(rt,0);
        work(rt);   printf("%d
",ans); 
    }
}

Pythonプログラミングの練習Numpyの使い方

python爬虫類捕まえ画像