結果
| 問題 |
No.1005 BOT対策
|
| コンテスト | |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-03-08 10:09:41 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 36 ms / 2,000 ms |
| コード長 | 6,949 bytes |
| コンパイル時間 | 1,533 ms |
| コンパイル使用メモリ | 116,196 KB |
| 実行使用メモリ | 28,272 KB |
| 最終ジャッジ日時 | 2025-06-20 00:50:28 |
| 合計ジャッジ時間 | 3,727 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using static Rh;
static class Program{
const int mod=(int)1e9+7;
static void Main(){
Sc sc=new Sc();
var s=sc.S;
var t=sc.S;
int ans=0;
if(t.Length==1){
for(int i = 0;i<s.Length;i++) {
if(t[0]==s[i]){
Console.WriteLine(-1);
return;
}
}
Console.WriteLine(0);
return;
}
Rh rh=new Rh();
var hs=new Hsa(s);
var ht=t;
for(int i = t.Length-1;i<s.Length;i++) {
if(hs.Get(i-t.Length+1,i)==ht){
ans++;
i+=t.Length-1;
if(t[0]==t[t.Length-1]){i--;}
}
}
Console.WriteLine("{0}",ans);
}
}
public class Rh{
public static readonly int mod1=1073741783,mod2=1073741789;
public static readonly int b1=1007,b2=1009+DateTime.Now.Millisecond;
private static long[] r1,r2;
private static int n;
public Rh(){n=0;}
public Rh(int n){
Rh.n=n;
r1=new long[n+1];
r2=new long[n+1];
r1[0]=r2[0]=1;
for(int i = 1;i<=n;i++) {
r1[i]=(r1[i-1]*b1)%mod1;
r2[i]=(r2[i-1]*b2)%mod2;
}
}
public class Hsa{
private Hs[] hs;
public int n;
public Hsa(int[] a){
n=a.Length;
if(n>Rh.n){
Rh.n=n;
r1=new long[n+1];
r2=new long[n+1];
r1[0]=r2[0]=1;
hs=new Hs[n+1];
hs[0]=new Hs(0);
for(int i = 1;i<=n;i++) {
r1[i]=(r1[i-1]*b1)%mod1;
r2[i]=(r2[i-1]*b2)%mod2;
hs[i]=hs[i-1]+a[i-1];
}
}
else{
hs=new Hs[n+1];
hs[0]=new Hs(0);
for(int i = 1;i<=n;i++) {hs[i]=hs[i-1]+a[i-1];}
}
}
public Hsa(string a){
n=a.Length;
if(n>Rh.n){
Rh.n=n;
r1=new long[n+1];
r2=new long[n+1];
r1[0]=r2[0]=1;
hs=new Hs[n+1];
hs[0]=new Hs(0);
for(int i = 1;i<=n;i++) {
r1[i]=(r1[i-1]*b1)%mod1;
r2[i]=(r2[i-1]*b2)%mod2;
hs[i]=hs[i-1]+a[i-1];
}
}
else{
hs=new Hs[n+1];
hs[0]=new Hs(0);
for(int i = 1;i<=n;i++) {hs[i]=hs[i-1]+a[i-1];}
}
}
public static implicit operator Hsa(int[] a){return new Hsa(a);}
public static implicit operator Hsa(string a){return new Hsa(a);}
public Hs Get(int a,int b){return hs[b+1]-hs[a];}
public int Bs(int a,int b){return Bs(a,b,n-Max(a,b));}
public int Bs(int a,int b,int ub){
int lb=-1,mid=0;
while(ub-lb>1){
mid=(ub+lb)/2;
if(Get(a,a+mid)!=Get(b,b+mid)){ub=mid;}
else{lb=mid;}
}
return ub;
}
public int Bsp(Hsa a){return Bsp(0,a);}
public int Bsp(int k,Hsa a){
int lb=-1,mid=0,ub=Min(n-k,a.n);
while(ub-lb>1){
mid=(ub+lb)/2;
if(Get(k,mid+k)!=a.Get(0,mid)){ub=mid;}
else{lb=mid;}
}
return ub;
}
public int Bss(Hsa a){return Bss(n-1,a);}
public int Bss(int k,Hsa a){
int lb=0,mid=0,ub=Min(k+1,a.n)+1;
while(ub-lb>1){
mid=(ub+lb)/2;
if(Get(k+1-mid,k)!=a.Get(a.n-mid,a.n-1)){ub=mid;}
else{lb=mid;}
}
return lb;
}
}
public struct Hs{
public long h1,h2;
public int d;
public Hs(int n){h1=h2=d=0;}
public static implicit operator bool(Hs h){return h.d>0;}
public static implicit operator Hs(string s){
Hs h=new Hs(0);
for(int i=0;i<s.Length;i++){h+=s[i];}
return h;
}
public static implicit operator Hs(int[] s){
Hs h=new Hs(0);
for(int i=0;i<s.Length;i++){h+=s[i];}
return h;
}
public static Hs operator+(Hs a,int c){
a.h1=(a.h1*b1+c)%mod1;
a.h2=(a.h2*b2+c)%mod2;
a.d++;
return a;
}
public static Hs operator+(Hs a,Hs p){
a.h1=(a.h1*r1[p.d]+p.h1)%mod1;
a.h2=(a.h2*r2[p.d]+p.h2)%mod2;
a.d+=p.d;
return a;
}
public static Hs operator-(Hs a,int c){
a.d--;
a.h1=(a.h1+mod1-(r1[a.d]*c%mod1))%mod1;
a.h2=(a.h2+mod2-(r2[a.d]*c%mod2))%mod2;
return a;
}
public static Hs operator-(Hs a,Hs p){
a.d-=p.d;
a.h1=(a.h1+mod1-(r1[a.d]*p.h1%mod1))%mod1;
a.h2=(a.h2+mod2-(r2[a.d]*p.h2%mod2))%mod2;
return a;
}
public static bool operator==(Hs a,Hs b){return a.h1==b.h1&&a.h2==b.h2&&a.d==b.d;}
public static bool operator!=(Hs a,Hs b){return a.h1!=b.h1||a.h2!=b.h2||a.d!=b.d;}
public override bool Equals(object obj){return false;}
public override int GetHashCode(){return 0;}
}
public class Hss{
public int n;
public Tuple<Hs,int>[] da;
public Hss(string[] s){
n=s.Length;
da=new Tuple<Hs,int>[n];
for(int i = 0;i<n;i++) {da[i]=Tuple.Create((Hs)s[i],i);}
Array.Sort(da,(u,v)=>u.Item1.h1.CompareTo(v.Item1.h1));
}
public int Eq(Hs h){
int lb=-1,mid=0,ub=n-1;
while(ub-lb>1){
mid=(ub+lb)/2;
if(da[mid].Item1.h1>=h.h1){ub=mid;}
else{lb=mid;}
}
for(int i = ub;i<n&&da[i].Item1.h1==h.h1;i++) {if(da[i].Item1==h){return da[i].Item2;}}
return -1;
}
}
}
public class Sc{
public int I{get{return int.Parse(Console.ReadLine());}}
public long L{get{return long.Parse(Console.ReadLine());}}
public double D{get{return double.Parse(Console.ReadLine());}}
public string S{get{return Console.ReadLine();}}
public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
public string[] Sa{get{return Console.ReadLine().Split();}}
public object[] Oa{get{return Console.ReadLine().Split();}}
public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}