[Codeforces 1025C] Plasticine zebra

[Codeforces 1025C] Plasticine zebra - 1600

문제 설명 : 

문자열에서 특정 연산이 하나 정의된다. 그 연산은 문자열 내에서 특정 인덱스 사이를 기준으로 양 옆의 문자열을 reverse하는 연산이다. 이 연산을 0번 이상 사용하여 나온 문자열에서 b,w가 교대로 최대 몇 번 등장할 수 있는지를 구하는 문제이다.

풀이 : 

결과적으로 '특정 연산'을 사용하게 되면 그 결과는 원본 문자열에서 몇 번 만큼 shift한 결과와 동일하다. 아직까지는 왜 이것이 가능한지는 밝히지 못했다. 따라서 나는 원본 문자열을 특정 횟수만큼 shift했을 때 최대 몇 번 b,w가 교대로 등장하는지만 세주면 된다. 이에 대한 구현은 원본 문자열 뒤에 똑같이 문자열을 붙여면 O(N)만에 수행할 수 있다.

주의할 점 : 

-

배울 점 : 

cyclic string이란 string의 구성 원소들을 rotate함으로써 얻을 수 있는 string을 의미한다. 예를 들어 "1234"의 cyclic string"은 "2341","3412","4123"이 있다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 100009;
 
string str;
 
int main(){
    cin>>str;
    int len=str.length();
 
    str=str+str;
 
    int ans=0,cnt=1;
    for(int i=0 ; str[i+1] ; i++){
        if(str[i]!=str[i+1]){
            cnt++;
        }
        else{
         ans=max(ans,cnt);
         cnt=1;
        }
    }
    ans=max(ans,cnt);
    ans=min(len,ans);
    printf("%d\n",ans);
 
    return 0;
}