Submission #1021865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021865		Almonther	Necklace (Subtask 1-3) (BOI19_necklace1)	C++98	0 / 85	2 ms	1100 KiB

necklace

#include <bits/stdc++.h>

#define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define co cout<<
//#pragma GCC optimize("O3,Ofast,unroll-loops")
//#pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
//stuff
const ll maxn=405,mod=1e9+7,base=3005;
string s,s1;
ll ha[maxn][maxn];
ll ha1[maxn][maxn];
void solve(){
    cin>>s>>s1;
    if(s.size()>s1.size()) swap(s,s1);
    s='#'+s;
    s1='#'+s1;
    for(int i=1;i<s.size();i++){
        ll freq[27]={};
        for(int j=i;j<s.size();j++){
            freq[s[j]-'a']++;
            for(int k=0;k<27;k++) ha[i][j]=(ha[i][j]*base+freq[k])%mod;
        }
    }
    for(int i=1;i<s1.size();i++){
        ll freq[27]={};
        for(int j=i;j<s1.size();j++){
            freq[s1[j]-'a']++;
            for(int k=0;k<27;k++) ha1[i][j]=(ha1[i][j]*base+freq[k])%mod;
        }
    }
    for(int k=s.size()-1;k>=1;k--){
        for(int i=1;i<s.size();i++){
            if(i+k-1>=s.size()) break;
            for(int j=1;j<s1.size()-k+1;j++){
                if(j+k-1>=s1.size()) break;
                if(ha[i][i+k-1]==ha1[j][j+k-1]){
                    // co ha[i][i+k-1]<<' '<<ha1[j][j+k-1]<<'\n';
                    // co s.substr(i,k)<<' '<<s1.substr(j,k)<<'\n';
                    co k<<'\n'<<i-1<<' '<<j-1;
                    return;
                }
            }
        }
    }
}
int main()
{
    suiii
    int tt=1;
    // cin>>tt;
    while(tt--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void solve()':
necklace.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=1;i<s.size();i++){
      |                 ~^~~~~~~~~
necklace.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int j=i;j<s.size();j++){
      |                     ~^~~~~~~~~
necklace.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=1;i<s1.size();i++){
      |                 ~^~~~~~~~~~
necklace.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j=i;j<s1.size();j++){
      |                     ~^~~~~~~~~~
necklace.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i=1;i<s.size();i++){
      |                     ~^~~~~~~~~
necklace.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             if(i+k-1>=s.size()) break;
      |                ~~~~~^~~~~~~~~~
necklace.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for(int j=1;j<s1.size()-k+1;j++){
      |                         ~^~~~~~~~~~~~~~
necklace.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 if(j+k-1>=s1.size()) break;
      |                    ~~~~~^~~~~~~~~~~

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