//기억하는 것도 좋지만 기억에 의존하면 생각할 여유를 잃을 수 있음.

#include <stdio.h>

#include <string.h>//only for initializing variables.

#define MAX_N 100

#define MAX_STR 10000

//2MB 미만..

char safe[MAX_N][MAX_STR+1]; // => 1 * 10000 * 100 + 1= 1,000,001 bytes

int p[MAX_STR]; //=> 4 * 10000 => 40,000 bytes

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

int N;

void makeDoubledString(const char* org,char* dst){

    int n_org = mystrlen(org);

    int i=0;

    for(i=0;i<n_org;i++){

        dst[i]=org[i];

    }

    for(i=0;i<=n_org;i++){

        dst[i+n_org] = org[i];

    }

}

void makeRevDoubledString(const char* org,char* dst){

    int n_org = mystrlen(org);

    int i=0;

    for(i=0;i<n_org;i++){

        dst[i]=org[n_org-i-1];

    }

    for(i=0;i<n_org;i++){

        dst[i+n_org] = org[n_org-i-1];

    }

    dst[i+n_org] = '\0';

}

void partialSearch(const char* N, int n){

    int begin = 1, match =0;

    while(begin + match < n){

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

            match ++;

            p[begin + match - 1] = match;

        }else if(!match){begin ++;}

        else{

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

            match = p[match - 1];

        }

    }

}

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

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

    partialSearch(N,ln);

    while(begin < lh - ln){

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

            match ++;

            if(match == ln){ return begin;}

        }else if(!match){begin++;}

        else{

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

            match = p[match -1 ];

        }

    }

    printf("Opps!

");

    return 0;

}

int main(){

    char doubleSafe[MAX_STR*2+1]; // => 1 * 20000 + 1= 20,001 bytes

    char reverseSafe[MAX_STR +1];

    int sum,i,j;

    N=3;

    strcpy(safe[0],"abbab");

    strcpy(safe[1],"babab");

    strcpy(safe[2],"ababb")\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0;

    strcpy(safe[3],"bbaba");

    N=2;

    strcpy(safe[0],"RMDCMRCD");

    strcpy(safe[1],"MRCDRMDC");

    strcpy(safe[2],"DCMRCDRM");

    int n_org = mystrlen(safe[0]);

    for(i=0,sum=0;i<N;i++){

        //시계방향

        if(i%2==0){

            makeDoubledString(safe[i+1],doubleSafe);

            sum += firstSearch(doubleSafe,safe[i]);    

        }else{

            //책방법

            //makeDoubledString(safe[i],doubleSafe);

            //sum += firstSearch(doubleSafe,safe[i+1]);    

            //내가푼방법..

            makeDoubledString(safe[i+1],doubleSafe);

            sum += n_org - firstSearch(doubleSafe,safe[i]);    

        }

    }

    printf("%d

",sum);

}

#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);

}