Submission #928855

#	Time	Username	Problem	Language	Result	Execution time	Memory
928855		Muhammad_Aneeq	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	1528 ms	648 KiB

necklace

/*
بسم الله الرحمن الرحيم
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;
  }
  reverse(begin(b),end(b));
  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;
              break;
            }
          }
        }
    }
  }
  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++)
      |                ~^~~~~~~~~
necklace.cpp:44: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]
   44 |   for (int i=0;i<b.size();i++)
      |                ~^~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40