Submission #928805

#TimeUsernameProblemLanguageResultExecution timeMemory
928805Muhammad_AneeqNecklace (Subtask 4) (BOI19_necklace4)C++17
0 / 15
1514 ms600 KiB
/* بسم الله الرحمن الرحيم Author: (:Muhammad Aneeq:) */ #include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std; #define int long long int mod=1e9+7; int power(int x,int y) { int res=1; while (y) { if (y&1) res=(res*x)%mod; x=(x*x)%mod; y>>=1; } return res; } string x,y; bool check(int i,int j,int k) { string a,b; for (int l=i;l<i+k;l++) a+=x[l]; for (int l=j;l<j+k;l++) b+=y[l]; reverse(begin(a),end(a)); for (int i=0;i<b.size();i++) { char g=b.back(); b.pop_back(); b=g+b; if (b==a) return 1; } return 0; } vector<int>pr={2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59,61,67,71,73,79,83,89,97,101}; inline void solve() { cin>>x>>y; int n=x.size(),m=y.size(); int hash[n+1]={}; int hash1[m+1]={}; hash[0]=hash1[0]=1; for (int i=0;i<n;i++) hash[i+1]=(hash[i]*pr[x[i]-'a'])%mod; for (int i=0;i<m;i++) hash1[i+1]=(hash1[i]*pr[y[i]-'a'])%mod; int ans=0,l,r; for (int k=1;k<=min(n,m);k++) { map<int,vector<int>>d; for (int i=0;i<=n-k;i++) { int z=(hash[i+k]*power(hash[i],mod-2))%mod; d[z].push_back(i); } for (int j=0;j<=m-k;j++) { int z=(hash1[j+k]*power(hash1[j],mod-2))%mod; if (d.find(z)!=d.end()) { if (ans<k) { if (check(d[z][0],j,k)) { ans=k; l=d[z][0],r=j; } } } } } cout<<ans<<endl; cout<<l<<' '<<r<<endl; } signed main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); solve(); }

Compilation message (stderr)

necklace.cpp: In function 'bool check(long long int, long long int, long long int)':
necklace.cpp:35:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i=0;i<b.size();i++)
      |                ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...