oj.uz

답안 #1076796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1076796 2024-08-26T16:40:56 Z vjudge1 Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 301 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first
#define se second
string s;
string t;
string s1,s2;
int L[3003],R[3003],dp1[3003],dp2[3003],m,n,k,cs1,cs2;
int maxx;
int riel(int x)
{
    return t.size()-1-x;
}
main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s;
    cin>>t;
    for (int i=0;i<s.size();++i)
    {
        s1=" ";
        s2=" ";
        for (int j=i;j>=0;--j) s1+=s[j];
        for (int j=i+1;j<s.size();++j) s2+=s[j];
        L[1]=0;
        k=0;
        m=s1.size()-1;
        n=s2.size()-1;
        for (int j=2;j<=m;++j)
        {
            while (k>0 && s1[j]!=s1[k+1]) k=L[k];
            if (s1[j]==s1[k+1]) L[j]=++k;
            else L[j]=0;
        }
        k=0;
        R[1]=0;
        for (int j=2;j<=n;++j)
        {
            while (k>0 && s2[j]!=s2[k+1]) k=R[k];
            if (s2[j]==s2[k+1]) R[j]=++k;
            else R[j]=0;
        }
        k=0;
        for (int j=0;j<t.size();++j)
        {
            while (k>0 && t[j]!=s2[k+1]) k=R[k];
            if (t[j]==s2[k+1]) dp1[j]=++k;
            else dp1[j]=0;
        }
        k=0;
        for (int j=t.size()-1;j>=0;--j)
        {
            while (k>0 && t[j]!=s1[k+1]) k=L[k];
            if (t[j]==s1[k+1]) dp2[j]=++k;
            else dp2[j]=0;
        }
        for (int j=0;j<t.size();++j)
        {
            if (maxx<dp1[j]+dp2[j+1])
            {
                maxx=dp1[j]+dp2[j+1];
                cs1=i-dp2[j+1]+1;
                cs2=j-dp1[j]+1;
            }
        }
    }
    reverse(t.begin(),t.end());
    for (int i=0;i<s.size();++i)
    {
        s1=" ";
        s2=" ";
        for (int j=i;j>=0;--j) s1+=s[j];
        for (int j=i+1;j<s.size();++j) s2+=s[j];
        L[1]=0;
        k=0;
        m=s1.size()-1;
        n=s2.size()-1;
        for (int j=2;j<=m;++j)
        {
            while (k>0 && s1[j]!=s1[k+1]) k=L[k];
            if (s1[j]==s1[k+1]) L[j]=++k;
            else L[j]=0;
        }
        k=0;
        R[1]=0;
        for (int j=2;j<=n;++j)
        {
            while (k>0 && s2[j]!=s2[k+1]) k=R[k];
            if (s2[j]==s2[k+1]) R[j]=++k;
            else R[j]=0;
        }
        k=0;
        for (int j=0;j<t.size();++j)
        {
            while (k>0 && t[j]!=s2[k+1]) k=R[k];
            if (t[j]==s2[k+1]) dp1[j]=++k;
            else dp1[j]=0;
        }
        k=0;
        for (int j=t.size()-1;j>=0;--j)
        {
            while (k>0 && t[j]!=s1[k+1]) k=L[k];
            if (t[j]==s1[k+1]) dp2[j]=++k;
            else dp2[j]=0;
        }
        for (int j=0;j<t.size();++j)
        {
            if (maxx<dp1[j]+dp2[j+1])
            {
                maxx=dp1[j]+dp2[j+1];
                cs1=i-dp2[j+1]+1;
                cs2=t.size()-1-(j+dp2[j+1]);
                //cout<<dp1[j]<<" "<<dp2[j+1]<<" "<<j<<'\n';
            }
        }
    }
    cout<<maxx<<'\n';
    cout<<cs1<<" "<<cs2;
    //cout<<dp2[6]<<" "<<dp1[5];
}

Compilation message

necklace.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main()
      | ^~~~
necklace.cpp: In function 'int main()':
necklace.cpp:21:19: 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 i=0;i<s.size();++i)
      |                  ~^~~~~~~~~
necklace.cpp:26:25: 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 j=i+1;j<s.size();++j) s2+=s[j];
      |                        ~^~~~~~~~~
necklace.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j=0;j<t.size();++j)
      |                      ~^~~~~~~~~
necklace.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int j=0;j<t.size();++j)
      |                      ~^~~~~~~~~
necklace.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i=0;i<s.size();++i)
      |                  ~^~~~~~~~~
necklace.cpp:75:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j=i+1;j<s.size();++j) s2+=s[j];
      |                        ~^~~~~~~~~
necklace.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j=0;j<t.size();++j)
      |                      ~^~~~~~~~~
necklace.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int j=0;j<t.size();++j)
      |                      ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 508 KB Output is correct
2 Correct 224 ms 344 KB Output is correct
3 Correct 301 ms 512 KB Output is correct
4 Correct 232 ms 344 KB Output is correct
5 Correct 117 ms 344 KB Output is correct
6 Correct 125 ms 504 KB Output is correct
7 Correct 175 ms 600 KB Output is correct
8 Correct 206 ms 500 KB Output is correct
9 Correct 223 ms 492 KB Output is correct