結果
| 問題 |
No.430 文字列検索
|
| コンテスト | |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-07-14 02:30:23 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 62 ms / 2,000 ms |
| コード長 | 10,592 bytes |
| コンパイル時間 | 3,665 ms |
| コンパイル使用メモリ | 110,720 KB |
| 実行使用メモリ | 29,696 KB |
| 最終ジャッジ日時 | 2024-11-10 00:45:03 |
| 合計ジャッジ時間 | 2,452 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 |
コンパイルメッセージ
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;
Sa sa=new Sa(s,'A','Z',true,true);
StringBuilder sb=new StringBuilder();
var n=sc.I;
long ans=0;
for(int i = 0;i<n;i++) {
var e=sa.Ft2(sc.S);
ans+=e.Item2+1-e.Item1;
}
Console.WriteLine(ans);
}
}
public class Sa{
private readonly int n,m,o;
public readonly string s;
public readonly int[] sa,lcp;
public readonly int[] da;
public readonly Spt lcps,sas1,sas2;
public Sa(string s,int a,int z,bool b1,bool b2){
m=z-a+2;
o=a-1;
s+=(char)o;
this.s=s;
n=s.Length;
da=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--) {
da[i]=s[i]!=s[i+1]?(s[i]>s[i+1]?1:0):da[i+1];
hi[s[i]-o]++;
if(da[i]==1&&da[i+1]==0){
da[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&&da[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&&da[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(da[sa[i]]==2){lh[j]=sa[i];j--;}
}
lcp=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++;}
lcp[lh[i]]=ki;
}
for(int i = c-1;i>=0;i--) {lmsc[c-i-1]=lcp[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]--;
sub[lh[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&&da[sa[i]-1]==1){
sub[sa[i]-1]=hc1[s[sa[i]-1]-o];
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&&da[sa[i]-1]!=1){
hc3[s[sa[i]-1]-o]--;
sub[sa[i]-1]=hc3[s[sa[i]-1]-o];
sa[hc3[s[sa[i]-1]-o]]=sa[i]-1;
}
}
lcp=new int[n];
for(int i = 0;i<n-1;i++) {
da[sa[i+1]]=i+1;
if(sub[i]==n-1){continue;}
int p=n-Max(i,sa[sub[i]+1]),q=0;
if(i!=0&&lcp[sub[i-1]]>1){lcp[sub[i]]=q=lcp[sub[i-1]]-1;}
for(;q<p;q++) {if(s[i+q]!=s[sa[sub[i]+1]+q]){break;}}
lcp[sub[i]]=q;
}
lcps=new Spt(lcp,false);
if(b1){sas1=new Spt(sa,false);}
if(b2){sas2=new Spt(sa,true);}
}
public int Fb1(string t){return Bs1(t);}
public int Fb2(string t){return Bsl1(t);}
public Tuple<int,int> Ft1(string t){
int p=Bs1(t);
return p==-1?Tuple.Create(-1,-2):Tuple.Create(p,Bs2(t)-1);
}
public Tuple<int,int> Ft2(string t){
int p=Bsl1(t);
return p==-1?Tuple.Create(-1,-2):Tuple.Create(p,Bsl2(t)-1);
}
public int Lb(int a,int l){
if(l==0||l>lcp[a]){return a;}
int lb=a,mid=0,ub=n-1;
while(ub-lb>1){
mid=(ub+lb)>>1;
if(lcps.Get(a,mid)<l){ub=mid;}
else{lb=mid;}
}
return ub;
}
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)>>1;
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)>>1;
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 Bsl1(string t){
int l=t.Length;
int lb=-1,ub=n,mid=(ub+lb)>>1,pr=mid;
int ti=0;
while(ti<l&&s[sa[mid]+ti]==t[ti]){ti++;}
if(ti>=l||s[sa[mid]+ti]>=t[ti]){ub=mid;}
else{lb=mid;}
while(ub-lb>1){
mid=(ub+lb)>>1;
int d=mid<pr?lcps.Get(mid,pr-1):lcps.Get(pr,mid-1);
if(d==ti){
while(ti<l&&s[sa[mid]+ti]==t[ti]){ti++;}
pr=mid;
if(ti>=l||s[sa[mid]+ti]>=t[ti]){ub=mid;}
else{lb=mid;}
}
else if(d<ti){
if(mid>pr){ub=mid;}
else{lb=mid;}
}
else{
if(mid>pr){lb=mid;}
else{ub=mid;}
}
}
return ti==l?ub:-1;
}
public int Fb3(string t){
int l=t.Length;
int lb=-1,ub=n,mid=(ub+lb)>>1,pr=mid;
int ti=0;
while(ti<l&&s[sa[mid]+ti]==t[ti]){ti++;}
if(ti>=l){return ti;}
if(s[sa[mid]+ti]>=t[ti]){ub=mid;}
else{lb=mid;}
while(ub-lb>1){
mid=(ub+lb)>>1;
int d=mid<pr?lcps.Get(mid,pr-1):lcps.Get(pr,mid-1);
if(d==ti){
while(ti<l&&s[sa[mid]+ti]==t[ti]){ti++;}
if(ti>=l){break;}
pr=mid;
if(s[sa[mid]+ti]>=t[ti]){ub=mid;}
else{lb=mid;}
}
else if(d<ti){
if(mid>pr){ub=mid;}
else{lb=mid;}
}
else{
if(mid>pr){lb=mid;}
else{ub=mid;}
}
}
return ti;
}
private int Bsl2(string t){
int l=t.Length-1;
int lb=-1,ub=n,mid=(ub+lb)>>1,pr=mid;
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;}
while(ub-lb>1){
mid=(ub+lb)>>1;
int d=mid<pr?lcps.Get(mid,pr-1):lcps.Get(pr,mid-1);
if(d==ti){
while(ti<l&&s[sa[mid]+ti]==t[ti]){ti++;}
pr=mid;
if(s[sa[mid]+ti]>t[ti]){ub=mid;}
else{lb=mid;}
}
else if(d<ti){
if(mid>pr){ub=mid;}
else{lb=mid;}
}
else{
if(mid>pr){lb=mid;}
else{ub=mid;}
}
}
return ub;
}
private int[] Fu2(int[] s,int m){
int n=s.Length;
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 Spt{
private readonly int[][] d;
private readonly int[] l;
private Func<int,int,int> Fu;
public Spt(int[] a,bool bo){
int n=a.Length,m=(int)Log(n,2)+1;
d=new int[m][];
d[0]=new int[n];
l=new int[n+1];
if(bo){Fu=(y,x)=>Max(y,x);}
else{Fu=(y,x)=>Min(y,x);}
for(int i=0;i<n;i++){
d[0][i]=a[i];
l[i+1]=l[i>>1]+1;
}
for(int i=1,k=1;i<m;i++,k<<=1){
int p=n+1-(k<<1);
d[i]=new int[p];
for(int j=0;j<p;j++){d[i][j]=Fu(d[i-1][j],d[i-1][j+k]);}
}
}
public int Get(int a,int b){
if(a>b){(a,b)=(b,a);}
int p=l[b-a];
return Fu(d[p][a],d[p][b+1-(1<<p)]);
}
}
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(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),int.Parse);}
public int[] Ia3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),int.Parse);}
public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
public long[] La3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),long.Parse);}
public long[] La3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),long.Parse);}
public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
public double[] Da3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).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;}
}