Submission #928833

#	Time	Username	Problem	Language	Result	Execution time	Memory
928833		Muhammad_Aneeq	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	7 ms	512 KiB

necklace

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
 
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
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 join(char a,char b)
{
  string s;
  s+=a;
  s+=b;
  return s;
}
map<string,int>d;
bool prime(int n)
{
  for (int i=2;i<=sqrt(n);i++)
    if (n%i==0)
      return 0;
  return 1;
}
inline void solve()
{
  string x,y;
  cin>>x>>y;
  int n=x.size(),m=y.size();
  int ans=0,l=0,r=0;
  for (int k=2;k<=min(n,m);k++)
  {
    map<int,vector<int>>pre;
    int hash=1;
    for (int i=0;i<k-1;i++)
      hash=(hash*d[join(x[i],x[i+1])])%mod;
    hash=(hash*d[join(x[k-1],x[0])])%mod;
    pre[hash].push_back(0);
    for (int i=k-1;i<n-1;i++)
    {
      hash=(hash*power(d[join(x[i],x[i-k+1])],mod-2))%mod;
      hash=(hash*power(d[join(x[i-k+1],x[i-k+2])],mod-2))%mod;
      hash=(hash*d[(join(x[i],x[i+1]))])%mod;
      hash=(hash*d[join(x[i+1],x[i-k+2])])%mod;
      pre[hash].push_back(i-k+2);
    }
    hash=1;
    for (int i=0;i<k-1;i++)
      hash=(hash*d[join(y[i+1],y[i])])%mod;
    hash=(hash*d[join(y[0],y[k-1])])%mod;
    if (pre.find(hash)!=pre.end())
    {
      ans=k;
      l=pre[hash][0];
      r=0;
      continue;
    }
    for (int i=k-1;i<m-1;i++)
    {
      hash=(hash*power(d[join(y[i-k+1],y[i])],mod-2))%mod;
      hash=(hash*power(d[join(y[i-k+2],y[i-k+1])],mod-2))%mod;
      hash=(hash*d[(join(y[i+1],y[i]))])%mod;
      hash=(hash*d[join(y[i-k+2],y[i+1])])%mod;
      if (pre.find(hash)!=pre.end())
      {
        ans=k;
        l=pre[hash][0];
        r=i-k+2;
        break;
      }
    }
  }
  cout<<ans<<endl;
  cout<<l<<' '<<r<<endl;
}
signed main()
{
    int k=2;
    for (char i='a';i<='z';i++)
      for (char j='a';j<='z';j++)
      {
        while (!prime(k))
          k++;
        d[join(i,j)]=k;
        k++;
      }
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);   
        solve();
}

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