#include <stdio.h>

#include <string.h>

#define MAX_N 100

int pi[MAX_N];

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

void calculateGetSuf(const char* str){

    int n = mystrlen(str);

    int begin = 1, match =0;

    while(begin + match < n){

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

            match++;

            pi[begin + match - 1] = match;

        }else if(match==0){ begin++;}

        else{

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

            match = pi[match -1 ];

        }

    }

}

int kmpSearchModified2MaxOverlap(const char* H,const char* N){

    calculateGetSuf(N);

    int lh = mystrlen(H), ln = mystrlen(N),begin = 0, match =0;

    while(begin < lh/*-ln*/){

        if(match < ln && H[begin + match] == N[match]){

            match++;

            if(match + begin == lh){

                printf("%d

",begin);

            }

        }else if(match==0){begin ++;}

        else{

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

            match = pi[match -1];

        }

    }

    return 0;

}

int main(){

    char str[MAX_N+1];

    char reverseStr[MAX_N+1];

    strcpy(str,"anon");

    int n= mystrlen(str);

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

        reverseStr[i] = str[n-i-1];

    }

    reverseStr[n]='\0';

    kmpSearchModified2MaxOverlap(str,reverseStr);

    return 0;

}

//이미 가장 긴 것을 찾았으니 그것의 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

");

    }

}