글 읽기 - 1254번 반례가 뭔지 모르겠습니다..

________________ 8년 전 0

알고리즘을 설명하자면,

asf라는 단어가 있으면

int cnt=0;

asf+s[cnt]=asfa 팰린드롬이 아니므로 넘어감. cnt++

asf+s[cnt]=asfs 팰린드롬이 아니지만 최소 길이를 채우기 위해선 asf에서 s까지만 체크하면 됨으로(asffsa가 되는걸 방지)

s를 추가하고 cnt를 0으로 초기화.

asfs+s[0]=asfsa 팰린드롬 O s.size()를 출력.

이런식의 알고리즘 인데요.

반례가 뭔지 모르겠네요..

#include <iostream>
using namespace std;
int re;
int check(string a)
{
    string w;
    for(int i=a.size()-1; i>=0; i--)
    w+=a[i];
     
    if(a==w)
    return 1;
}
int process(string s,int swi)
{
  int cnt=0,len=s.size(),stk=0;
    while(1)
    {
       string tmp;
        
       tmp=s;
        
       tmp+=s[cnt];
        
       if(check(tmp)==1)
       return tmp.size();
       else
       {
       if(cnt!=len-2-stk-swi)    
       cnt++; 
       else{
       if(stk>re)
       return 100000;
       s+=s[cnt-stk],cnt=0,len=s.size(),stk++;
        
       if(check(s)==1)
       return len;      
       }
       }
    }
     
}
 
 
int main()
{
    int cnt=0,stk=0;
    string s;
     
    cin >> s;
     
    re=s.size();
     
    if(check(s)==1)
    cout << s.size();
    else
    cout << min(process(s,0),process(s,1)) << "\n";
}