제출 #13644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13644		dohyun0324	원형 문자열 (IZhO13_rowords)	C++98	100 / 100	170 ms	46588 KiB

rowords

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int dap,maxi,n,m,p,d[4010][4010],lena,lenb,par[4010][4010];
char a[4010],b[4010];
void lcs(int x)
{
    int i=n+x+1,j=m,cnt=0;
    while(1)
    {
        if(i==x+1 && j==0) break;
        if(par[i][j]==1) i--;
        else if(par[i][j]==2) j--;
        else if(par[i][j]==3) i--, j--;
        cnt++;
    }
    if(dap<n+m-cnt) dap=n+m-cnt;
}
void pro()
{
    int i,j,x,y;
    //make edge
    for(i=1;i<=n*2;i++)
    {
        for(j=1;j<=m;j++)
        {
            maxi=-2147483647;
            if(maxi<d[i][j-1]) maxi=d[i][j-1], p=2;
            if(maxi<d[i-1][j-1]+(a[i]==b[j])) maxi=d[i-1][j-1]+1, p=3;
            if(maxi<d[i-1][j]) maxi=d[i-1][j], p=1;
            par[i][j]=p; d[i][j]=maxi;
        }
    }
    for(i=1;i<=m;i++) par[0][i]=2;
    for(i=1;i<=n*2;i++) par[i][0]=1;
    if(dap<d[n][m]) dap=d[n][m];
    for(i=0;i<n;i++)
    {
        //remove first row
        for(j=1;j<=m;j++)
        {
            if(par[i+1][j]==3) break;
        }
        x=i+1; y=j;
        for(j=y;j<=m;j++) par[i+1][j]=2;
        //merge two tree
        while(x<2*n && y<=m)
        {
            if(par[x+1][y]==1)
            {
                par[x+1][y]=2;
                x++;
            }
            else if(par[x+1][y+1]==3)
            {
                par[x+1][y+1]=2;
                x++; y++;
            }
            else y++;
        }
        lcs(i);
    }
}
int main()
{
    int i;
    scanf("%s",a+1); n=strlen(a+1);
    scanf("%s",b+1); m=strlen(b+1);
    for(i=n+1;i<=n*2;i++) a[i]=a[i-n];
    pro();
    reverse(a+1,a+n*2+1);
    pro();
    printf("%d",dap);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

rowords.cpp: In function 'int main()':
rowords.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",a+1); n=strlen(a+1);
     ~~~~~^~~~~~~~~~
rowords.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",b+1); m=strlen(b+1);
     ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100