# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
928859 | 2024-02-17T07:08:57 Z | UmairAhmadMirza | Necklace (Subtask 1-3) (BOI19_necklace1) | C++14 | 4 ms | 7000 KB |
#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; } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7000 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7000 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7000 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |