//이미 가장 긴 것을 찾았으니 그것의 presuf 의 가장 긴 것을 찾는 방식으로 간다.

//KMP는 아직은 완벽하지 않으니 필요한 부분은 암기라도 해야함.

#include <stdio.h>

#include <string.h>

#define N 100

int p[N+1];

inline int mystrlen(const char* str){int n=0; for(n=0;str[n]!='\0';n++);return n;}

void getPreSuffix(const char *str){

    int n = mystrlen(str);

    int begin = 1;

    int match = 0;

    while(begin + match < n){

        if(str[begin + match] == str[match]){

            match ++;

            p[begin + match - 1] = match;

        }else if(match == 0){

            begin ++;

        }else{

            //K = matched - (matched -k)

            //p[match - 1] = match - k

            begin += match - p[match - 1];

            match = p[match - 1];

        }

    }

}

int main(){

    char str[N+1];

    strcpy(str,"ababbaba");

    getPreSuffix(str);

    int n = mystrlen(str);

    int k=0;

    for(k=p[n-1];k>0;k=p[k-1]){

        printf("%d

",k);

    }

    printf("%d

",n);

}

//Queue 나 Stack 은 잊지 않았지만.

//잔실수에 괜한 시간을 빼앗기는 것은 서두르기 때문;

#include <stdio.h>

#include <Windows.h>

#define MAX_K 5000000

short queue[5000000]; //2 * 5,000,000 = 10,000,000 bytes

int head =0;

int tail =0;

unsigned int sum =0;

short pop(){

    head ++;

    if(head<=tail){

        sum -= (unsigned int)queue[head];

        return queue[head];

    }else{

        head =tail;

        return -1;

    }

}

void push(short val){

    tail ++;

    if(tail < 5000000){

        queue[tail] = val;

        sum += (unsigned int)val;

    }else{

        tail --;

    }

}

//K : 합이 되는 수

//N : 20 개 중에

int getPartialSeq(unsigned int k,int n){

    head = 0;

    tail = 0;

    sum = 0u;

    int count=0;

    int i=0,j=0;

    unsigned int val=0;

    unsigned int cur = 0;

    cur = 1983u;

    for(i=1;i<n;i++){

        val = cur;

        cur = (cur * 214013u + 2531011u);

        val = val%(10000u)+1;

        push(val);

        //숫자 합이 k 보다 크면 point 를 하나 크게 한다. => pop

        while(sum > k){

            pop();

        }

        if(sum == k){

            count ++;

        }

    }

    return count;

}

int main(){

    long start = GetTickCount();

    printf("%d

",getPartialSeq(8791u,20));

    printf("%d

",getPartialSeq(5265u,5000));

    for(int i=0;i<20;i++){

    printf("%d

",getPartialSeq(3578452u,5000000));

    }

    printf("%.2lf sec

",(GetTickCount() - start)/1000.0);

}

//stack 기본 문제였던듯?

//그래도 마무리는 깔끔하게 모두 pop 되었는지, 전역변수는 제대로 초기화가 되었는지 확인!

#include <stdio.h>

#include <string.h>

inline int mystrlen(char* str){int n =0 ;for(n=0;str[n]!='\0';n++); return n;}

char bracket[10000];

char stack[10000];

int point=0;

char pop(){

    if(point<=0){return -1;}

    point--;

    return stack[point];

}

void push(char c){

    stack[point]=c;

    point++;

}

char well_formed(){

    int n = mystrlen(bracket);

    for(int i=0;i<n;i++){

        //열면 push

        //닫으면 pop

        if(bracket[i] == '['|| bracket[i] == '{'||bracket[i] == '('){

            push(bracket[i]);

        }else{

            char c = pop();

            if(bracket[i]==']'&& c != '[' ){

                return (char)0;

            }

            else if(bracket[i]=='}'&& c != '{'){

                    return (char)0;

            }else if(bracket[i]==')'&& c != '('){

                    return (char)0;

            }

        }

    }

    if(pop()==-1){

        return (char)1;

    }else{

        return (char)0;

    }

}

int main(){

    strcpy(bracket,"()()");

    point =0;

    if(well_formed()==(char)1){

        printf("YES

");

    }else{

        printf("NO

");

    }

    strcpy(bracket,"({[}])");

    point =0;

    if(well_formed()==(char)1){

        printf("YES

");

    }else{

        printf("NO

");

    }

    strcpy(bracket,"({}[(){}])");

    point =0;

    if(well_formed()==(char)1){

        printf("YES

");

    }else{

        printf("NO

");

    }

}

//최적화 없이 O(NK) 였음..

#include <stdio.h>

#define N 1000 //min 3

#define K 1000 //min 3

//1,4,2,6

int main(){

    //2명이 될때 까지 K 번 건너뛰면서 본다.

    int n =40;

    int k =3;

    int soldier[N];

    for(int i=0;i<n;i++){

        soldier[i] = 1;

    }

    int check =n;

    int no=0;

    while ( check >2){

        if(soldier[no]==1){

            check--;

            soldier[no] = 0;

        }else{

            int j=no+1;

            j=j%n;

            for(;soldier[j]==0;){

                j++;

                j=j%n;

            }

            no=j;

            check--;

            soldier[no] = 0;

        }

        for(int next = no+1,count =0;count <k;next++){

            next = next%n;

            if(soldier[next]==1){

                no = next;

                count++;

            }

        }

    }

    int j=0;

    for(int i=0;i<n;i++){

        if(soldier[i]){

        printf("%d ",i+1);

        j++;

        if(j==2){

            break;

        }

        }

    }

    printf("

");

}