Passion is like genius; a miracle.

이거 그 유명한 Algorithms on strings, trees and sequences 책의 연습 문제 중 하나입니다.

For each of the n prefixes of P, we want to know whether the prefix P[1..i] is a periodic string. That is, for each I we want to know the largest k > 1 (if there is one) such that P[1..i] can be written as αk for some string α. Of course, we also want to know the period. Show how to determine this for all n prefixes in time linear in the length of P.
Hint: Z-algorithm

저는 풀긴했는데 왜 되는건지 저도 잘 -_-;
너무 복잡하게 푼거 같네요.

이름을 modified-z value 라고 지어서 처리했는데, 사실 Z-algorithm 하고는 별 상관없고.. (처음 의도는 그랬지만 결국 상관없게 되버린..)

O(n)이라는건 돌려보면 쉽게 알 수 있습니다. 그게 아니라도 그냥 for 문만 봐도 i가 n까지만 돌아가니까 알 수 있어요.

#include<stdio.h>
#include<malloc.h>
#include<string.h>

// dump modified_z values
void dump(const char *p, int *modified_z, int len);

// print periods of P
void print_periods(int *modified_z, int len);

int main()
{
    const char *p = "abcabcd";

    int *modified_z = (int *) calloc(strlen(p), sizeof(int));
    int i, j, z_index;

    printf("P: %s\n", p);

    for (i=1, j=z_index=0 ; i < strlen(p) ; )
    {
        int z_index = i;
        {
            printf("comparing p[%d]=%c / p[%d]=%c\n", i, p[i], j, p[j]);
            if (p[i] == p[j])
            {
                modified_z[z_index]++;
                j++; i++;
            }
            else {
                z_index = i;
                i++;
                j=0;
            }
        }
    }

    dump(p, modified_z, strlen(p));

    print_periods(modified_z, strlen(p));

    return 0;
}

void print_periods(int *modified_z, int len)
{
    int i;
    int sum = 0;
    int non_zero = -1;
    int alpha_len = 0;

    for (i = 0 ; i < len ; i++)
    {
       if (modified_z[i] == 0)
        {
            non_zero = -1;
            sum = 0;
            alpha_len = 0;
        }
        else if (modified_z[i] != 0 && non_zero == -1)
        {
            non_zero = i;
        }

        if (modified_z[i] != 0)
        {
            sum += modified_z[i];
            if (non_zero == sum)
            {
                if (alpha_len == 0) alpha_len = non_zero;

                printf("P[1..%d] is alpha^%d.\n", i+1, (i+1)/alpha_len);
                printf("Got alpha. So, change non_zero from %d to -1\n", non_zero);
                non_zero=-1;
            }
        }

        printf("i=%d non_zero=%d alpha_len=%d sum=%d\n", i, non_zero, alpha_len, sum);
    }
}

void dump(const char *p, int *modified_z, int len)
{
    int i;
    for (i = 0 ; i < len ; i++)
        printf("%c\t modified_z[%d] = %d\n", p[i], i+1, modified_z[i]);
}
     // If this is the first time to find non zero MZ value
        else if (modified_z[i] != 0 && non_zero == -1)
        {
            // Remember the position where non zero MZ value were found
            non_zero = i;
        }

        // Non zero MZ position is found
        if (modified_z[i] != 0)
        {
            // Compute the number of successive matches
            sum += modified_z[i];

            // If the start of non zero position equals to the number of
            // successive matches.
            if (non_zero == sum)
            {
                // If this is the first time we found match after (1)
                // set the length of alpha as non_zero
                if (alpha_len == 0) alpha_len = non_zero;

                // Print matching information
                printf("Matching found\n");
                printf("P[1..%d] is alpha^%d.\n", i+1, (i+1)/alpha_len);

                // We want to find the next match
                non_zero=-1;
            }
        }

        printf("i=%d non_zero=%d alpha_len=%d sum=%d\n", i, non_zero, alpha_len, sum);
    }
}

//  Show me the contents of MZ
void dump(const char *p, int *modified_z, int len)
{
    int i;
    for (i = 0 ; i < len ; i++)
        printf("%c\t modified_z[%d] = %d\n", p[i], i+1, modified_z[i]);
}