結果
問題 | No.430 文字列検索 |
ユーザー | fgwiebfaoish |
提出日時 | 2020-04-05 05:55:30 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 7,579 bytes |
コンパイル時間 | 1,534 ms |
コンパイル使用メモリ | 109,952 KB |
実行使用メモリ | 19,968 KB |
最終ジャッジ日時 | 2024-11-10 00:42:06 |
合計ジャッジ時間 | 2,627 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 21 ms
18,048 KB |
testcase_01 | AC | 36 ms
19,968 KB |
testcase_02 | AC | 29 ms
18,816 KB |
testcase_03 | AC | 31 ms
19,968 KB |
testcase_04 | AC | 22 ms
18,048 KB |
testcase_05 | AC | 23 ms
17,920 KB |
testcase_06 | AC | 22 ms
18,176 KB |
testcase_07 | AC | 23 ms
18,304 KB |
testcase_08 | AC | 30 ms
19,584 KB |
testcase_09 | AC | 21 ms
18,176 KB |
testcase_10 | AC | 23 ms
18,304 KB |
testcase_11 | AC | 36 ms
19,712 KB |
testcase_12 | AC | 36 ms
19,712 KB |
testcase_13 | AC | 37 ms
19,840 KB |
testcase_14 | AC | 35 ms
19,584 KB |
testcase_15 | AC | 33 ms
19,584 KB |
testcase_16 | AC | 28 ms
19,072 KB |
testcase_17 | AC | 27 ms
18,816 KB |
コンパイルメッセージ
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; static class Program{ const int mod=(int)1e9+7; const double eps=1e-11; static void Main(){ Sc sc=new Sc(); var s=sc.S; var n=sc.I; Sa sa=new Sa(s,'A','Z'); int ans=0; for(int i = 0;i<n;i++) { var t=sc.S; var e=sa.Ft(t); ans+=e.Item2+1-e.Item1; } Console.WriteLine("{0}",ans); } } public class Sa{ private readonly int n,m,o; public readonly string s; public readonly int[] sa; public Sa(string s,int a,int z){ m=z-a+2; o=a-1; s+=(char)o; this.s=s; n=s.Length; int[] h=new int[n]; var lms=new List<int>(); int[] sub=new int[n]; int[] hi=new int[m]; int[] hc1=new int[m]; int[] hc2=new int[m]; int[] hc3=new int[m]; hi[s[n-1]-o]=hc2[s[n-1]-o]=hc3[s[n-1]-o]=1; for(int i = n-2,k=n-1;i>=0;i--) { h[i]=s[i]!=s[i+1]?(s[i]>s[i+1]?1:0):h[i+1]; hi[s[i]-o]++; if(h[i]==1&&h[i+1]==0){ h[i+1]=2; lms.Add(i+1); sub[i+1]=k-i; k=i+1; } } for(int i = 1;i<m;i++) { hi[i]+=hi[i-1]; hc2[i]=hc3[i]=hi[i]; hc1[i]=hi[i-1]; } int c=lms.Count; sa=new int[n]; for(int i = 0;i<c;i++) { hc2[s[lms[i]]-o]--; sa[hc2[s[lms[i]]-o]]=lms[i]; } for(int i = 0;i<n;i++) { if(sa[i]>0&&h[sa[i]-1]==1){ sa[hc1[s[sa[i]-1]-o]]=sa[i]-1; hc1[s[sa[i]-1]-o]++; } } for(int i = n-1;i>=0;i--) { if(sa[i]>0&&h[sa[i]-1]!=1){ hc3[s[sa[i]-1]-o]--; sa[hc3[s[sa[i]-1]-o]]=sa[i]-1; } } int[] lh=new int[c]; for(int i = 0,j=c-1;i<n&&j>=0;i++) { if(h[sa[i]]==2){lh[j]=sa[i];j--;} } int[] lmsz=new int[n]; int[] lmsc=new int[c]; bool jf=false; int ki=0; for(int i = c-2;i>=0;i--) { if(sub[lh[i]]==sub[lh[i+1]]){ bool bo=false; for(int j = 0;j<sub[lh[i]];j++) {if(s[lh[i]+j]!=s[lh[i+1]+j]){bo=true;break;}} if(bo){ki++;} else{jf=true;} } else{ki++;} lmsz[lh[i]]=ki; } for(int i = c-1;i>=0;i--) {lmsc[c-i-1]=lmsz[lms[i]];} hc2[0]=hc3[0]=hi[0]; hc1[0]=0; for(int i = 1;i<m;i++) { hc2[i]=hc3[i]=hi[i]; hc1[i]=hi[i-1]; } if(jf){ lh=Fu2(lmsc,ki+1); for(int i = 0;i<c;i++) {lh[i]=lms[c-1-lh[i]];} } sa=new int[n]; for(int i = 0;i<c;i++) { hc2[s[lh[i]]-o]--; sa[hc2[s[lh[i]]-o]]=lh[i]; } for(int i = 0;i<n;i++) { if(sa[i]>0&&h[sa[i]-1]==1){ sa[hc1[s[sa[i]-1]-o]]=sa[i]-1; hc1[s[sa[i]-1]-o]++; } } for(int i = n-1;i>=0;i--) { if(sa[i]>0&&h[sa[i]-1]!=1){ hc3[s[sa[i]-1]-o]--; sa[hc3[s[sa[i]-1]-o]]=sa[i]-1; } } } public int Fb(string t){return Bs1(t);} public Tuple<int,int> Ft(string t){ int p=Bs1(t); return p==-1?Tuple.Create(-1,-2):Tuple.Create(p,Bs2(t)-1); } private int Bs1(string t){ int l=t.Length-1; int lb=-1,mid=0,ub=n-1; while(ub-lb>1){ mid=(ub+lb)/2; int ti=0; while(ti<l&&s[sa[mid]+ti]==t[ti]){ti++;} if(s[sa[mid]+ti]>=t[ti]){ub=mid;} else{lb=mid;} } bool bo=true; for(int i = 0;i<=l;i++) {if(s[sa[ub]+i]!=t[i]){bo=false;break;}} return bo?ub:-1; } private int Bs2(string t){ int l=t.Length; int lb=-1,mid=0,ub=n; while(ub-lb>1){ mid=(ub+lb)/2; int tm=Min(l,n-sa[mid])-1,ti=0; while(s[sa[mid]+ti]==t[ti]&&ti<tm){ti++;} if(s[sa[mid]+ti]>t[ti]){ub=mid;} else{lb=mid;} } return ub; } private int[] Fu2(IReadOnlyList<int> s,int m){ int n=s.Count; var lms=new List<int>(); int[] h=new int[n],sub=new int[n],sa=new int[n]; int[] hi=new int[m],hc1=new int[m],hc2=new int[m],hc3=new int[m]; hi[s[n-1]]=hc2[s[n-1]]=hc3[s[n-1]]=1; for(int i = n-2,k=n-1;i>=0;i--) { h[i]=s[i]!=s[i+1]?(s[i]>s[i+1]?1:0):h[i+1]; hi[s[i]]++; if(h[i]==1&&h[i+1]==0){ h[i+1]=2; lms.Add(i+1); sub[i+1]=k-i; k=i+1; } } int lm=lms.Count; for(int i = 1;i<m;i++) { hi[i]+=hi[i-1]; hc2[i]=hc3[i]=hi[i]; hc1[i]=hi[i-1]; } for(int i = 0;i<lm;i++) { hc2[s[lms[i]]]--; sa[hc2[s[lms[i]]]]=lms[i]; } for(int i = 0;i<n;i++) { if(sa[i]>0&&h[sa[i]-1]==1){ sa[hc1[s[sa[i]-1]]]=sa[i]-1; hc1[s[sa[i]-1]]++; } } for(int i = n-1;i>=0;i--) { if(sa[i]>0&&h[sa[i]-1]!=1){ hc3[s[sa[i]-1]]--; sa[hc3[s[sa[i]-1]]]=sa[i]-1; } } int[] sl=new int[lm]; for(int i = 0,j=lm-1;i<n&&j>=0;i++) { if(h[sa[i]]==2){sl[j]=sa[i];j--;} } int[] lmsz=new int[n]; bool jf=false; int ki=0; for(int i = lm-2;i>=0;i--) { if(sub[sl[i]]==sub[sl[i+1]]){ bool bo=false; for(int j = 0;j<sub[sl[i]];j++) {if(s[sl[i]+j]!=s[sl[i+1]+j]){bo=true;break;}} if(bo){ki++;} else{jf=true;} } else{ki++;} lmsz[sl[i]]=ki; } int[] lmsc=new int[lm]; for(int i = lm-1;i>=0;i--) {lmsc[lm-i-1]=lmsz[lms[i]];} hc2[0]=hc3[0]=hi[0]; hc1[0]=0; for(int i = 1;i<m;i++) { hc2[i]=hc3[i]=hi[i]; hc1[i]=hi[i-1]; } if(jf){ sl=Fu2(lmsc,ki+1); for(int i = 0;i<lm;i++) {sl[i]=lms[lm-1-sl[i]];} } sa=new int[n]; for(int i = 0;i<lm;i++) { hc2[s[sl[i]]]--; sa[n-1-hc2[s[sl[i]]]]=sl[i]; } for(int i = n-1;i>=0;i--) { if(sa[i]>0&&h[sa[i]-1]==1){ sa[n-1-hc1[s[sa[i]-1]]]=sa[i]-1; hc1[s[sa[i]-1]]++; } } for(int i = 0;i<n;i++) { if(sa[i]>0&&h[sa[i]-1]!=1){ hc3[s[sa[i]-1]]--; sa[n-1-hc3[s[sa[i]-1]]]=sa[i]-1; } } return sa; } } 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;} }