제출 #928859

#제출 시각아이디문제언어결과실행 시간메모리
928859UmairAhmadMirzaNecklace (Subtask 1-3) (BOI19_necklace1)C++14
0 / 85
4 ms7000 KiB
#include <iostream> using namespace std; #define int long long int const N=405; int const mod=1e9+7; int const base=727; int hsh1[N][N]; int hsh2[N][N]; int r_hsh1[N][N]; int r_hsh2[N][N]; int min_hsh1[N][N]; int min_hsh2[N][N]; // map<int,bool> mp1; // map<int,bool> mp2; int pw[N]; string a,b; void make_hash1(){ int n=a.length(); for(int i=1;i<=n;i++){ int h1=0; for(int j=i;j<=n;j++){ h1*=base; h1%=mod; h1+=a[j-1]; h1%=mod; hsh1[i][j]=h1; } } for(int i=n;i>=1;i--){ int h1=0; for(int j=i;j>=1;j--){ h1*=base; h1%=mod; h1+=a[j-1]; h1%=mod; r_hsh1[j][i]=h1; } } } void make_hash2(){ int n=b.length(); for(int i=1;i<=n;i++){ int h1=0; for(int j=i;j<=n;j++){ h1*=base; h1%=mod; h1+=b[j-1]; h1%=mod; hsh2[i][j]=h1; } } for(int i=n;i>=1;i--){ int h1=0; for(int j=i;j>=1;j--){ h1*=base; h1%=mod; h1+=b[j-1]; h1%=mod; r_hsh2[j][i]=h1; } } } void set_hsh1(){ int n=a.length(); int h=0; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){ min_hsh1[i][j]=hsh1[i][j]; for(int k=i;k<=j;k++){ h=(hsh1[k][j]*pw[k-i])%mod; h+=hsh1[i][k-1]; h%=mod; min_hsh1[i][j]=min(min_hsh1[i][j],h); } // cout<<i<<' '<<j<<' '<<min_hsh1[i][j]<<endl; } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){ min_hsh2[i][j]=hsh2[i][j]; for(int k=i;k<=j;k++){ h=(r_hsh1[i][k]*pw[j-k])%mod; h+=r_hsh1[k+1][j]; h%=mod; min_hsh1[i][j]=min(min_hsh1[i][j],h); } // cout<<i<<' '<<j<<' '<<min_hsh1[i][j]<<endl; } } void set_hsh2(){ int n=b.length(); int h=0; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){ for(int k=i;k<=j;k++){ h=(hsh2[k][j]*pw[k-i])%mod; h+=hsh2[i][k-1]; h%=mod; min_hsh2[i][j]=min(min_hsh2[i][j],h); } // cout<<i<<' '<<j<<' '<<min_hsh2[i][j]<<endl; } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){ for(int k=i;k<=j;k++){ h=(r_hsh2[i][k]*pw[j-k])%mod; h+=r_hsh2[k+1][j]; h%=mod; min_hsh2[i][j]=min(min_hsh2[i][j],h); } // cout<<i<<' '<<j<<' '<<min_hsh2[i][j]<<endl; } } void pwer(){ pw[0]=1; for(int i=1;i<N;i++) pw[i]=(pw[i-1]*base)%mod; } signed main() { cin>>a>>b; pwer(); make_hash1(); make_hash2(); set_hsh1(); set_hsh2(); int n=a.length(); for(int l=n-1;l>=0;l--) for(int i=1;i<=(n-l);i++) for(int j=1;j<=(b.length())-l;j++){ if(min_hsh1[i][i+l]==min_hsh2[j][j+l]){ cout<<l+1<<endl; cout<<i<<' '<<j<<endl; return 0; } } }

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'int main()':
necklace.cpp:132:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  132 |       for(int j=1;j<=(b.length())-l;j++){
      |                   ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...